相较于无向图，有向图的部分性质使用起来比较麻烦。在介绍之前，先给出有向图(DiGraph)的定义。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
42
43
44public 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 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];
}
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;
}
}
这个定义与无向图相比主要是在addEdge方法中有差别，由于有了方向性，所以不能再双向添加。
有向图中有一个经典问题，那就是有向图的可达性，给点一个或一组点，是否存在从给点的点出发到达终点的路径。
解决这类问题用到了深度优先搜索(DFS)。
代码：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
34public 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];
}
public static void main(String[] args) {
Digraph G = new Digraph(new In(args[0]));
Bag<Integer> sources = new Bag<Integer>();
for(int i=1;i<args.length;i++)
sources.add(Integer.parseInt(args[i]));
DirectedDFS reachable = new DirectedDFS(G,sources);
for(int v=0;v<G.V();v++)
if(reachable.marked(v))
StdOut.print(v+" ");
StdOut.println();
}
}
分析：
基本上与深度优先搜索一致，都是将当前访问点进行标记，然后进行递归访问。
在判断有向图是否可达之后还有一个问题值得关注，那就是当前的有向图是否有环。
有关这个问题我们可以构造一个栈用于存放在深度优先搜索过程中访问过的点，如果在后续访问中出现了v->w且w已经在栈中的情况，则说明之前w已经被访问过了，而此时又有别的路径访问到w，则可断定出现了环。
代码：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
42
43
44
45public 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;
}
private boolean hasCycle(){
return cycle!=null;
}
public Iterable<Integer> cycle(){
return cycle;
}
}
分析：
检测有向环主要在dfs方法中。首先，从起点出发，这时就将起点入栈，并将其标记为已访问，随后便进入v的邻接结点，对于没有访问过的结点都进行标记操作并继续dfs，最后得到的结果就是所有被访问过的点都会入栈，此时执行第二个else if，此时如果结点w出现在栈中，则代表之前已经被访问过，也就是出现了环。当从起点出发的结点都被访问过之后，则将其设为false。
在检测有向图是否有环后就能对有向图进行顶点排序。
排序的方式有多种，包括前序、后序和逆后续。
代码：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
38public 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;
}
}
其中，前序和后续使用队列进行存储，而逆后续利用栈的性质进行存储。
接下来谈论的一个排序是拓扑排序，所谓拓扑排序就是对存在前后关系的图进行线性排序，每次输出的数据都是入度为0的结点。这个排序可以用来进行处理任务调度之类的问题。
代码：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
28public 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;
}
public static void main(String[] args) {
String filename = args[0];
String separator = args[1];
SymbolDigraph sg = new SymbolDigraph(filename,separator);
Topological top = new Topological(sg.G());
for(int v:top.order)
StdOut.println(sg.name(v));
}
}
由于一幅有向无环图的拓扑顺序就是所有顶点的逆后序排序，所以直接调用逆后序排序即可。
至于为什么拓扑排序就是逆后序排序，因为对于任意边v->w，在调用dfs(v)时，一定会出现以下情况。
- dfs(w)已经被调用且已经返回；
- dfs(w)还没有被调用，这样就会因为被直接或间接调用返回dfs(w)，且dfs(w)会在dfs(v)返回前返回；
- dfs(w)已经被调用但还未返回，但是这种情况不会出现，因为在有向无环图中，如果出现被调用却未返回的情况，则代表存在w到v的路径，这样就与无环相冲突。
综上所述，dfs(w)都会在dfs(v)之前完成，所以使用逆后序排序的话就能让w排在v之后输出，达到前提条件先被输出的效果。
这其中的缺少的数据结构，比如Queue、Bag可以到http://algs4.cs.princeton.edu/code 下载。