4.2 有向图

4.2 有向图

定义:边是单向的,每条边连接的两个顶点是一个有序对,邻接性也是单向的

4.2.1 术语表

• 有向路径
• 有向环

4.2.2 有向图API:public class Digraph

4.2.2.1 有向图的表示:邻接表

Digraph数据类型

import edu.princeton.cs.algs4.In;
public class Digraph {
    private final int V;//点集
    private int E;//有向边集
    private Bag<Integer>[] adj;
    public Digraph(int V) {
        this.V = V;
        E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int i = 0; i < V; i++)
            adj[i] = new Bag<>();
    }
    public Digraph(In in){
        this(in.readInt());
        int E = in.readInt();
        for (int i = 0; i < E; i++){
            int v = in.readInt();
            int w = in.readInt();
            addEdge(v, w);
        }
    }
    public int V() { return V; }
    public int E() { return E; }
    public void addEdge(int v, int w) {
        adj[v].add(w);
        E++;
    }
    public Iterable<Integer> adj(int v) { return adj[v]; }//返回V指向所有结点
    public Digraph reverse() {
        Digraph R = new Digraph(V);
        for (int v = 0; v < V; v++)
            for (int w : adj(v))
                R.addEdge(w, v);
        return R;
    }
}

4.2.3 有向图中的可达性(算法4.4)

4.2.4 环和有向无环图(算法4.5)

4.2.5 有向图的强连通性(算法4.6)

4.2.6 总结

• 4.2中接触到的各种有向图算法只有一种非基于DFS | 问题 | 解决方法 | 参考 | | :—-: | :—-: | :—-: | | 单点/多点可达性 | DirectedDFS | 算法4.4 | | 单点有向路径 | DepthFirstDirectedPaths | 算法4.1(换名) | | 单点最短有向路径 | BreadthFirstDirectedPath | 算法4.2(换名) | | 有向环检测 | DirectedCycle | 算法4.5 | | 深度优先顶点排序 | DirectedFirstOrder | 算法4.5 | | 优先级调度问题 | Topological | 算法4.5 | | 拓扑排序 | Topological | 算法4.5 | | 强连通性 | KosarajuSCC | 算法4.6 | | 顶点对可达性 | TransitiveClosure | 算法4.6 |