引言
在有向圖相關的實際應用中，有向環特别重要。一幅圖可能含有大量的環，通常，我們一般隻關注它們是否存在。
有關圖的概念可參考博文資料結構之圖的概述
在學習環之前，我們一起來學習下排程問題。
排程問題
給定一組任務并安排它們的執行順序，限制條件為這些任務的執行方法、起始時間以及任務的消耗等。最重要的一種限制條件叫做優先級限制，它指定了哪些任務必須在哪些任務之前完成。不同類型的限制條件會産生不同難度的排程問題。
以一個正在安排課程的大學生為例，有些課程是其他課程的先導課程。如上圖所示。
比如要學習機器學習(Machine Learning)，得先學習人工智能(Artificial Intelligence)。
再假設該同學一次隻能選修一門課程，就會遇到下面的問題：
** 優先級限制下的排程問題**：在滿足限制條件的情況下如何安排并完成所有任務。我們可以畫出一張有向圖，頂點對應任務（通過數組索引來表示課程），有向邊對應優先級順序。
上圖9代表人工智能，11代表機器學習。
而在有向圖中，優先級限制下的排程問題等價于拓撲排序：
拓撲排序：給定一副有向圖，将所有的頂點排序，使得所有的有向邊均從排在前面的頂點指向排在後面的頂點。
上圖為示例的拓撲排序，所有的邊都是向下的。按照這個順序，該同學可以在滿足先導課程限制的條件下選修完所有課程。
有向圖中的環
如果任務x必須在任務y之前完成:x→y,而y→z，同時z→x。那麼就會形成一個環：x→y→z→x。如果一個有優先級限制的問題中存在有向環，那麼這個問題肯定是無解的。是以我們需要首先進行有向環檢測。
有向環檢測：檢測給定的有向圖是否包含環，若有環，通常隻需找出一個即可。
有向無環圖(DAG):不含環的有向圖
可以轉換為檢查一副有向圖是否為有向無環圖。
對課程圖進行一些修改，增加一些環如上所示。
尋找環利用了DFS方法，維護一個遞歸調用期間已通路的頂點的棧，若(在遞歸調用期間，通過判斷
onStack
标記數組)兩次通路了某個頂點，則說明有環；若DFS遞歸調用完畢，說明無環。
該遞歸調用期間隻是遞歸dfs調用它的鄰接頂點期間(如果有鄰接頂點，它的鄰接頂點也會執行同樣的過程，是以會越來越深)，一旦遞歸完它的所有鄰接頂點，會把該頂點從 onStack
我們暫且關注0-5六個頂點。執行圖解如下：
初始化3個數組，分别表示是否已通路、路徑上的上一個頂點、是否為遞歸調用期間棧上的頂點
首先
dfs(0)
,将
标記為已通路，并将
的調用棧标記置為
true
，然後遞歸的通路
的鄰接點
1
。觀察到
1
沒有通路過,将
1
的上一個節點置為
。
dfs(1)
，将
1
标記為已通路，并将
1
的調用棧标記置為
true
，因為
1
無鄰接點，
dfs(1)
調用完畢，并将
1
的調用棧标記置為
false
(在圖中用空白表示
false
)，回退到
dfs(0)
遞歸調用
的下一個鄰接點
5
,将
5
的上一節點置為
遞歸調用
dfs(5)
将
5
标記為已通路，并将
5
的調用棧标記置為
true
遞歸的通路
5
的鄰接點
4
。觀察到
4
沒有通路過,将其上一節點置為
5
，然後調用
dfs(4)
，将
4
标記為已通路，并将
4
的調用棧标記置為
true
，遞歸的通路
4
的鄰接點
2
，觀察到
2
沒有通路過
将
2
上一節點置為
4
，遞歸調用
dfs(2)
将
2
标記為已通路，并将
2
的調用棧标記置為
true
，遞歸的通路
2
的鄰接點
，觀察到
已經通路過，且
在調用棧中,是以發現了環。 此時已經得出結果可以傳回了，但别急，我們将環的路徑存入調用棧中，友善後面輸出。
cycle
環棧輸入順序為：2,4,5,0
找到的環為：2→0→5→4→2
檢測有向圖是否有環代碼
package com.algorithms.graph;
import com.algorithms.stack.Stack;
/**
* @author yjw
* @date 2019/5/20/020
*/
public class DirectedCycle {
private boolean[] marked;
private int[] edgeTo;
/**
* 有向環中的所有頂點(如果存在)
*/
private Stack<Integer> cycle;
/**
* 儲存遞歸調用期間棧上的所有頂點
*/
private boolean[] onStack;
public DirectedCycle(DiGraph g) {
marked = new boolean[g.vertexNum()];
edgeTo = new int[g.vertexNum()];
onStack = new boolean[g.vertexNum()];
for (int v = 0; v < g.vertexNum(); v++) {
if (!marked[v]) {
dfs(g, v);
}
}
}
private void dfs(DiGraph g, int v) {
marked[v] = true;
onStack[v] = true;
for (int w : g.adj(v)) {
if (hasCycle()) {
//有環直接退出
return;
} else if (!marked[w]) {
edgeTo[w] = v;
dfs(g, w);
} else if (onStack[w]) {
//如果w已經在棧中，說明再一次通路到了w，是以此時發現了環
cycle = new Stack<>();
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(int v) {
return cycle;
}
public static void main(String[] args) {
DiGraph g = new DiGraph(13);
g.addDiEdges(0, 5, 1);
g.addDiEdges(2, 3, 0);
g.addDiEdges(3, 2, 5);
g.addDiEdges(4, 3, 2);
g.addDiEdges(5, 4);
g.addDiEdges(6, 0, 4, 9);
g.addDiEdges(7, 6, 8);
g.addDiEdges(8, 7, 9);
g.addDiEdges(9, 10, 11);
g.addDiEdges(10, 12);
g.addDiEdges(11, 4, 12);
g.addDiEdges(12, 9);
//System.out.println(g);
DirectedCycle dc = new DirectedCycle(g);
if (dc.hasCycle()) {
for (int w : dc.cycle) {
System.out.print(w + "->");
}
}
}
}
接下來一起學習下有向圖的拓撲排序，在學習如何拓撲排序之前，我們先了解下圖的前序、後序、以及逆後序周遊。
因為拓撲排序和上述中某周遊序列有千絲萬縷的關系。
頂點的深度優先順序
圖的深度優先搜尋隻會通路每個頂點一次，如果将
dfs(int v)
的參數頂點
v
儲存在一個資料結構中，
周遊這個資料結構實際上就能通路圖中的所有頂點。
周遊的順序取決于該資料結構的性質(棧的先進後出、隊列的先進先出)，以及是在遞歸調用之前還是之後存入該資料結構。
常見的的3種周遊順序如下：
- 前序：在遞歸調用之前将頂點加入隊列
- 後序：在遞歸調用之後将頂點加入隊列
- 逆後序：在遞歸調用之後将頂點壓入棧
我們以上面這個圖為例，對該圖進行3種周遊：
pre
和
post
是隊列，
reversePost
是棧，紅色元素為最近插入的元素。從左到右，可以看到隊列是先進先出，而棧是先進後出。
分析下執行過程，首先調用
dfs(0)
,
的鄰接點為{2},在遞歸調用
dfs(2)
之前，将
入前序隊列；
調用
dfs(2)
，
2
的鄰接點為{0,1,3}，因為
剛才已經通路過，不會遞歸調用
，是以會繼續遞歸調用
1
(将它入前序隊列)，它沒有鄰接點，遞歸
dfs
調用
1
的鄰接點完畢，将
1
入後序隊列；
然後繼續調用
2
的下一個鄰接點
3
，而
3
又會導緻
dfs(4)
和
dfs(5)
，該兩個頂點都沒有鄰接點，是以很快就可以傳回，
3
的所有鄰接點遞歸調用完畢，到了
3 done
。後面也是一樣，
2
和
依次調用完畢。
有向圖的前序、後序周遊代碼
package com.algorithms.graph;
import com.algorithms.queue.Queue;
import com.algorithms.stack.Stack;
/**
* 頂點的深度優先順序
* @author yjw
* @date 2019/5/21/021
*/
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<>();
post = new Queue<>();
reversePost = new Stack<>();
marked = new boolean[g.vertexNum()];
for (int v = 0; v < g.vertexNum(); v++) {
if (!marked[v]) {
dfs(g,v);
}
}
}
private void dfs(DiGraph g, int v) {
marked[v] = true;
//前序：遞歸調用dfs之前将頂點加入隊列
pre.enqueue(v);
for (int w : g.adj(v)) {
if (!marked[w]) {
//遞歸調用dfs
dfs(g, w);
}
}
//周遊完所有的鄰接點後(遞歸調用dfs之後)
//後序：遞歸調用dfs之後将頂點加入隊列
post.enqueue(v);
//逆後序：在遞歸調用dfs之後将頂點壓入棧
reversePost.push(v);
}
public Iterable<Integer> pre() {
return pre;
}
public Iterable<Integer> post() {
return post;
}
public Iterable<Integer> reversePost() {
return reversePost;
}
public static void main(String[] args) {
DiGraph g = new DiGraph(6);
g.addEdge(0,2,2,0,2,1,2,3,3,2,3,4,3,5);
DepthFirstOrder dfo = new DepthFirstOrder(g);
for (Integer v: dfo.pre()){
System.out.print(v + " ");
}
System.out.println();
for (Integer v: dfo.post()){
System.out.print(v + " ");
}
System.out.println();
for (Integer v: dfo.reversePost()){
System.out.print(v + " ");
}
System.out.println();
/**
* 輸出:
* 0 2 1 3 4 5
* 1 4 5 3 2 0
* 0 2 3 5 4 1
*/
}
}
拓撲排序
回顧一下拓撲排序的描述
拓撲排序：給定一副有向圖，将所有的頂點排序，使得所有的有向邊均從排在前面的頂點指向排在後面的頂點。
上圖為示例的拓撲排序，所有的邊都是向下的。按照這個順序，可以在滿足先導課程限制的條件下選修完所有課程。
一副有向無環圖的拓撲排序即為所有頂點的逆後序排列
package com.algorithms.graph;
/**
* 有向無環圖的拓撲排序即為所有頂點的逆後序排列
*
* @author yjw
* @date 2019/5/21/021
*/
public class Topological {
//頂點的拓撲順序
private Iterable<Integer> order;
public Topological(DiGraph g) {
//首先檢測是否有環
DirectedCycle cycle = new DirectedCycle(g);
if (!cycle.hasCycle()) {
DepthFirstOrder dfs = new DepthFirstOrder(g);
order = dfs.reversePost();
}
}
public Iterable<Integer> order() {
return order;
}
/**
* 是否為有向無環圖
*
* @return
*/
public boolean isDAG() {
return order != null;
}
public static void main(String[] args) {
DiGraph g = new DiGraph(13);
g.addDiEdges(0, 1, 5, 6);
g.addDiEdges(2, 0, 3);
g.addDiEdges(3, 5);
g.addDiEdges(5, 4);
g.addDiEdges(6, 4, 9);
g.addDiEdges(7, 6);
g.addDiEdges(8, 7);
g.addDiEdges(9, 10, 11,12);
g.addDiEdges(11, 12);
Topological tp = new Topological(g);
if (tp.isDAG()) {
for (Integer v : tp.order) {
System.out.print(v + " ");
}
}
}
}