相關概念
AOV網
AOV網（Activity On Vertex Network）用頂點表示活動。邊是無權的，僅僅用來表示前驅與後繼關系。
前驅與後繼
有向邊的起點稱為終點的前驅，有向邊的終點稱為起點的後繼。拓撲排序的關注點在于前驅——一個結點的前驅結點全部被通路過後，該結點才能被通路。
拓撲序列
對一個有向無環圖G進行拓撲排序，是将G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊<u,v>∈E(G)，則u線上性序列中出現在v之前。
>_< 看個圖了解一下上面的定義吧！！！
拓撲排序算法（DFS）
▼ 課程表是否合理（是否存在拓撲序列？有向圖是否有環？）
【DFS判環】
思路: 在DFS過程中标記染色，如果出現閉環立即判錯
使用一個visted[]數組（我更喜歡稱其為draw數組）：
* 0 表示未被通路過
* 1 表示正在通路中，即在"本次"DFS路徑中正在被通路，當再次通路到該處，說明出現閉環
* -1 表示"絕對安全"，即某次DFS直到結束也沒有出現閉環，當再次通路到該處，直接可以認為從該處開始沒有閉環
private boolean hasLoop(List<List<Integer>> graph, int n) {
// 多從DFS共用一個draw數組
int[] draw = new int[n];
// 考慮到圖可能不完全連通，需要從每個點開始一次DFS
for (int i = 0; i < n; i++) {
if (!DFS(graph, i, draw)) {
return false;
}
}
return true;
}
/**
* 0 表示未被通路過
* 1 表示正在通路中，即在本次DFS路徑中正在被通路，當再次通路到該處，說明出現閉環
* -1 表示絕對安全，即某次DFS直到結束也沒有出現閉環，當再次通路到該處，直接可以認為從該處開始沒有閉環
*/
private boolean DFS(List<List<Integer>> graph, int cur, int[] draw) {
if (draw[cur] == 1) { // 出現閉環，直接判false
return false;
}
if (draw[cur] == -1) { // 從該點開始絕對安全，直接判true
return true;
}
draw[cur] = 1; // cur點标記為正在本次DFS路徑中
for (int nxt : graph.get(cur)) {
if (!DFS(graph, nxt, draw)) {
return false;
}
}
draw[cur] = -1; // 從cur開始的DFS徹底結束，标記cur點絕對安全
return true;
}
▼ 排出一個合理的課程表（生成拓撲序列）
【DFS生成拓撲序列】
由上面的DFS代碼轉化而來：
1. 用一個成員變量記錄是否有環
2. 用一個棧結構存放拓撲序列
3. 每次判定出一個結點"絕對安全"時，就可以入棧。
private int[] topologicalSort(List<List<Integer>> graph, int n) {
// 多從DFS共用一個draw數組
int[] draw = new int[n];
// 考慮到圖可能不完全連通，需要從每個點開始一次DFS
for (int i = 0; i < n; i++) {
DFS(graph, i, draw);
}
// 取出拓撲序列
if (hasLoop) {
return new int[0];
} else {
int[] res = new int[n];
int index = 0;
while (!stack.isEmpty()) {
res[index] = stack.pop();
}
return res;
}
}
private ArrayDeque<Integer> stack = new ArrayDeque<>(); // 用棧記錄拓撲序列
private boolean hasLoop = false; // 是否有環
private void DFS(List<List<Integer>> graph, int cur, int[] draw) {
if (draw[cur] == 1) {
hasLoop = true;
return;
}
if (draw[cur] == -1) {
return;
}
draw[cur] = 1;
for (int nxt : graph.get(cur)) {
DFS(graph, nxt, draw);
}
draw[cur] = -1;
stack.push(cur); // 絕對安全後，cur入棧
}
拓撲排序算法（BFS）
▼ 課程表是否合理（是否存在拓撲序列？有向圖是否有環？）
【BFS判環】
思路: 使用degree[]入度數組，一個結點入度為0說明它的前驅結點都已完成
1. 初始化入度數組
2. 入度為0的結點先入隊
3. 開始BFS，每取出一個結點即學習完一個結點，将它指向的所有結點入度減1
4. 如果入度減一後變為0，則該結點入隊
5. 每次進行入隊操作時，便計數+1，如果最後入隊的次數等于總結點數，說明所有結點都已完成，無環
private boolean hasLoop(List<List<Integer>> graph, int n) {
// 初始化入度數組
int[] degree = new int[n];
for (int i = 0; i < n; i++) {
for (int j : graph.get(i)) {
degree[j]++;
}
}
// 初始化隊列（将入度為0的結點加入隊列中）
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 0) {
queue.offer(i);
}
}
// BFS，每取出一個結點即學習完一個結點，将它指向的所有結點入度減1
int count = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int nxt : graph.get(cur)) {
degree[nxt]--;
if (degree[nxt] == 0) {
queue.offer(nxt);
count++;
}
}
}
// 如果所有結點都被通路過(學習過)，則說明存在拓撲序列
return count == n;
}
▼ 排出一個合理的課程表（生成拓撲序列）
【BFS判環】
由上面的BFS代碼轉化而來
1. 用一個暫存隊列記錄拓撲序列（别和DFS用的隊列搞混了）
2. 每次有結點入隊時，就将它加到暫存隊列中，最後再把暫存隊列轉化為拓撲序列
3. 如果隊列的長度等于結點的總個數，則傳回序列；否則說明有環，無合法拓撲序列
private boolean hasLoop(List<List<Integer>> graph, int n) {
// 初始化入度數組
int[] degree = new int[n];
for (int i = 0; i < n; i++) {
for (int j : graph.get(i)) {
degree[j]++;
}
}
// 最終結果，下标兼具計數的作用
int[] res = new int[n];
int count = 0;
// 初始化隊列（将入度為0的結點加入隊列中）
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 0) {
queue.offer(i);
res[count++] = i;
}
}
// BFS，每取出一個結點即學習完一個結點，将它指向的所有結點入度減1
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int nxt : graph.get(cur)) {
degree[nxt]--;
if (degree[nxt] == 0) {
queue.offer(nxt);
res[count++] = nxt;
}
}
}
// 如果隊列的長度等于結點的總個數，則傳回序列；否則說明有環，無合法拓撲序列
return count == n ? res : new int[0];
}
補充說明
❶ 我們發現，DFS和BFS是兩種不同的思路——【DFS+染色數組】VS【BFS+入度數組】
❷【生成拓撲序列】的代碼實作直接在【判環】的代碼基礎上修改就行了
❸ 生成拓撲序列時，我們應當意識到DFS和BFS的一個重要差別：
- DFS是一個逆向生成序列的過程。 比如1 → 3 → 5，在DFS時，從1開始遞歸，但1最後完成遞歸。我們會依次得到5，3，1，是以這個記錄序列的資料結構我們使用棧（Stack）
- BFS是一個正向生成序列的過程。 比如1 → 3 → 5，在BFS時，入度為0的1先入隊，之後3，5依次入度減為0而入隊。我們會依次得到1，3，5，是以這個記錄序列的資料結構我們使用隊列（Queue）
☘️
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)