4.2.1　术语

由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点

4.2.2　有向图的数据类型

public class Digraph
Digraph(int V)创建一幅含有V个顶点但没有边的有向图
Digraph(In in)从输入流 in 中读取一幅有向图
int V()顶点总数
int E()边的总数
void addEdge(int v, int w)向有向图中添加一条边 v → w
Iterable adj(int v)由 v 指出的边所连接的所有顶点
Digraph reverse()该图的反向图
String toString()对象的字符串表示
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Digraph
{
    private final int V;
    private int E;
    private Bag<Integer>[] adj;
    public Digraph(int V)
    {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[v];
        for(int v=0;v<V;v++)
            adj[v] = new Bag<Integer>();
    }
    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];}
    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　有向图中的可达性

public class DirectedDFS
DirectedDFS(Digraph G, int s)在 G 中找到从s可达的所有顶点
DirectedDFS(Digraph G,Iterable sources)在 G 中找到从sources中的所有顶点可达的所有顶点
boolean marked(int v)v 是可达的吗
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class DirectedDFS
{
    private boolean[] marked;
    public DirectedDFS(Digraph G, int s)
    {
        marked = new boolean[G.V()];
        dfs(G, s);
    }
    public DirectedDFS(Digraph G, Iterable<Integer> sources)
    {
        marked = new boolean[G.V()];
        for (int s : sources)
            if (!marked[s]) dfs(G, s);
    }
    private void dfs(Digraph G, int v)
    {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
    }
    public boolean marked(int v) { return marked[v]; }
}

4.2.3.1　标记 - 清除的垃圾收集

4.2.4　环和有向无环图

4.2.4.1　调度问题

拓扑排序：给定一幅有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素（或者说明无法做到这一点）

4.2.4.2　有向图中的环

有向环检测：给定的有向图中包含有向环吗？如果有，按照路径的方向从某个顶点并返回自己来找到环上的所有顶点

public class DirectedCycle
DirectedCycle(Digraph G)寻找有向环的构造函数
boolean hasCycle()G 是否含有有向环
Iterable cycle()有向环中的所有顶点（如果存在的话）
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class DirectedCycle{
    private boolean[] marked;
    private int[] edgeTo;
    private Stack<Integer> cycle; //有向环中的所有顶点（如果存在）
    private boolean[] onStack; //递归调用的栈上的所有顶点
    public DirectedCycle(Digraph G){
        onStack = new boolean[G.V()];
        edgeTo = new int[G.V()];
        marked = new boolean[G.V()];
        for(int v=0;v<G.V();v++)
            if(!marked[v]) dfs(G,v);
    }
    private void dfs(Digraph G,int v){
        onStack[v] = true;
        marked[v] = true;
        for(int w:G.adj(v))
            if(this.hasCycle()) return;
            else if(!marked[w]) {edgeTo[w] = v; dfs(G, w);}
            else if(onStack[w]){
                cycle = new Stack<Integer>();
                for(int x = v;x!=w;x=edgeTo[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
            }
        onStack[v]=false;
    }
    public boolean hasCycle(){return cycle != null;}
    public Iterable<Integer> cycle(){return cycle;}
}

4.2.4.3　顶点的深度优先次序与拓扑排序

public class Topological
Topological(Digraph G)拓扑排序的构造函数
boolean isDAG()G 是有向无环图吗
Iterable order()拓扑有序的所有顶点
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class DepthFirstOrder{
    private boolean[] marked;
    private Queue<Integer> pre; //所有顶点的前序排序
    private Queue<Integer> post; //所有顶点的后序排序
    private Stack<Integer> reversePost; //所有顶点的递后序排序
    public DepthFirstOrder(Digraph G){
        pre = new Queue<Integer>();
        post = new Queue<Integer>();
        reversePost = new Stack<Integer>();
        marked = new boolean[G.V()];
        for(int v=0;v<G.V();v++)
            if(!marked[v]) dfs(G,v);
    }
    private void dfs(Digraph G,int v){
        pre.enqueue(v);
        marked[v] = true;
        for(int w:G.adj(v))
            if(!marked[w]) {dfs(G, w);}
        post.enqueue(v);
        reversePost.push(v);
    }
    public Iterable<Integer> pre(){return pre;}
    public Iterable<Integer> post(){return post;}
    public Iterable<Integer> reversePost(){return reversePost;}
}

public class Topological
{
    private Iterable<Integer> order; // 顶点的拓扑顺序
    public Topological(Digraph G)
    {
        DirectedCycle cyclefinder = new DirectedCycle(G);
        if (!cyclefinder.hasCycle())
        {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost();
        }
    }
    public Iterable<Integer> order() { return order; }
    public boolean isDAG() { return order != null; }
}

4.2.5　有向图中的强连通性

两个顶点v和w互相可达