有向图的实现

小半 • 2023年2月3日上午10:55 • 技术随笔 • 阅读 149

一.概述

定义：
有向图是一副具有方向性的图，是由一组顶点和一组有方向的边组成的，每条方向的边都连着一对有序的顶点。

出度：
由某个顶点指出的边的个数称为该顶点的出度。

入度：
指向某个顶点的边的个数称为该顶点的入度。

有向路径：
由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点。

有向环：
一条至少含有一条边，且起点和终点相同的有向路径。

一副有向图中两个顶点v和w可能存在以下四种关系：

没有边相连；
存在从v到w的边v—>w;
存在从w到v的边w—>v;
既存在w到v的边，也存在v到w的边，即双向连接；

注意：有向图的邻接表表示的是， 从当前顶点出发，能够到达的相邻的顶点！

二.有向图的实现

反向图的思路:
将已存在的v→w的边（v的邻接表中），使用addEdge方法，添加w→v的边添加至一个新的图对象即可。

public class Digraph {
    private final int V; //记录顶点数量
    private int E;   //边数量
    private Queue<Integer>[] adj; //邻接表 ，索引为顶点， 每个Queue为对应顶点的 相邻顶点

    public Digraph(int v) {
        this.V = v;
        this.E = 0;  //默认图中是没有边的，后用add添加边
        this.adj = new Queue[v];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new LinkedList<>(); //初始化邻接表，每一个元素是一个队列

        }
    }

    public void addEdge(int v, int w) {  //给有向图添加 v→w 的一条边
        adj[v].add(w);  //只让w出现在v的邻接表中，仅表示从v指向w ！
    }

    public Queue adj(int v) {  //获取与顶点v相邻的所有顶点
        return adj[v];
    }

    public Digraph reverse() { //该图的反向图
        Digraph r = new Digraph(V);//顶点数量不变，建立一个新的图对象（用自己所在的类建立对象！）
        for (int v = 0; v < V; v++) { //遍历每个顶点（adj的索引）
           for (Integer w : adj[v]) {//遍历每个顶点下的队列！ 得到从v出发指向的相邻顶点w
                r.addEdge(w, v);  //向r图中添加从w指向v的边，即完成反向操作
            }
        }
        return r;
    }

    public int V() {
        return this.V;
    }

    public int E() {
        return this.E;
    }
}