在 AOV 網(wǎng)中，若從節(jié)點 i 到節(jié)點 j 存在一條有向路徑，則稱節(jié)點 i 是節(jié)點 j 的前驅(qū)，或者稱節(jié)點 j 是節(jié)點 i 的后繼。若<i,j>是圖中的弧，則稱節(jié)點 i 是節(jié)點 j 的直接前驅(qū)，節(jié)點 j 是節(jié)點 i 的直接后繼。

在 AOV 網(wǎng)中弧表示了活動之間存在的制約關(guān)系。例如，計算機專業(yè)的學生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè)。學生按照怎樣的順序來學習這些課程呢？

課程的名稱與相應編號如下表所示。

課程編號	課程名稱	先修課程
C	程序設(shè)計基礎(chǔ)	無
C1	數(shù)據(jù)結(jié)構(gòu)	C0、C2
C2	離散數(shù)學	C0
C3	高級程序設(shè)計	C0、C
C4	數(shù)值分析	C2、C3、C5
C5	高等數(shù)學	無

如果用節(jié)點表示課程，用弧表示先修關(guān)系，若課程 i 是課程 j 的先修課程，則用弧<i,j>表示，課程之間的關(guān)系如下圖所示。

在 AOV 中不允許有環(huán)，否則會出現(xiàn)自己是自己的前驅(qū)情況，陷入死循環(huán)。怎么判斷在 AOV 網(wǎng)中是否有環(huán)呢？一種檢測的辦法就是對有向圖中的節(jié)點進行拓撲排序。如果 AOV 網(wǎng)中的所有節(jié)點都在拓撲序列中，則在 AOV 網(wǎng)中必定無環(huán)。

2.拓撲排序

拓撲排序指將 AOV 網(wǎng)中的節(jié)點排成一個線性序列，該序列必須滿足：若從節(jié)點 i 到節(jié)點 j 有一條路徑，則在該序列中節(jié)點 i 一定在節(jié)點 j 之前。

拓撲排序的基本思想：

1 選擇一個無前驅(qū)的節(jié)點并輸出。

2 從圖中刪除該節(jié)點和該節(jié)點所有發(fā)出邊。

3 重復步驟1、2,直到不存在無前驅(qū)的節(jié)點。

4 如果輸出的節(jié)點數(shù)少于 AOV 網(wǎng)中節(jié)點數(shù)，則說網(wǎng)中有環(huán)，否則輸出的序列即拓撲序列。

拓撲排序并不是唯一的，例如上圖中，節(jié)點 C0 和 C5 都無前驅(qū)，先輸出哪一個都可以。

下面圖解是其中一種刪除順序。

拓撲序列為：C0、C5、C3、C2、C1、C4

在上述過程中有刪除節(jié)點和邊的操作，實際上，沒必要真的刪除節(jié)點和邊?？梢詫]有前驅(qū)的節(jié)點（入度為0）暫存到棧中，輸出時出棧即表示刪除。進行邊的刪除時將其鄰接點的入度減1即可。例如下圖中刪除 C0 的所有發(fā)出邊，相對于 C3、C2、C1 節(jié)點入度減1。

3.算法步驟

1 求各節(jié)點的入度，將其存入數(shù)組 indegree[] 中，并將入度為 0 的節(jié)點入棧 S。

2 如果棧不空，則重復執(zhí)行以下操作：將棧頂元素 i 出棧并保存到拓撲序列數(shù)組 topo[] 中；將節(jié)點 i 的所有鄰節(jié)點入度都減 1，如果減 1 后入度為 0，則立即入棧 S。

3 如果輸出的節(jié)點數(shù)少于 AOV 網(wǎng)中的節(jié)點數(shù)，則說明網(wǎng)中有環(huán)，否則輸出拓撲序列。

4.圖解

AOV 網(wǎng)如下圖所示。

1 輸入邊時，累加節(jié)點入度并保存到數(shù)組 indegree[] 中，將入度為0 的節(jié)點入棧 S。

2 將棧頂元素 5 出棧并保存到拓撲序列數(shù)組 topo[] 中。將節(jié)點 5 的所有鄰接點(C3、C4)入度都減1，如果減1后，入度為0，則立即入棧 S。

3 將棧頂元素 0 出棧并保存到拓撲序列數(shù)組 topo[] 中。將節(jié)點 0 的所有鄰接點(C1、C2、C4)入度都減1，如果減1后，入度為0，則立即入棧 S。

4 將棧頂元素 3 出棧并保存到拓撲序列數(shù)組 topo[] 中。將節(jié)點 3 的所有鄰接點(C4)入度都減1，如果減1后，入度為0，則立即入棧 S。

5 將棧頂元素 2 出棧并保存到拓撲序列數(shù)組 topo[] 中。將節(jié)點 2 的所有鄰接點(C1、C4)入度都減1，如果減1后，入度為0，則立即入棧 S。

6 將棧頂元素 4 出棧并保存到拓撲序列數(shù)組 topo[] 中。節(jié)點 4 沒有鄰接點。

7 將棧頂元素 1 出棧并保存到拓撲序列數(shù)組 topo[] 中。節(jié)點 1 沒有鄰接點。

8 ?？眨惴ㄍＶ?。輸出拓撲排序序列。

拓撲排序算法實現(xiàn)

1.拓撲圖

2.實現(xiàn)代碼

package graph.topoSort;
 
import java.util.Scanner;
import java.util.Stack;
 
public class TopoSort {
    static final int maxn = 105;
    static int map[][] = new int[maxn][maxn];
    static int indegree[] = new int[maxn];
    static int topo[] = new int[maxn];
    static int n, m;
    static Stack<Integer> s = new Stack<>();
 
    static boolean TopoSort() { // 拓撲排序
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (indegree[i] == 0)
                s.push(i);
        while (!s.empty()) {
            int u = s.peek();
            s.pop();
            topo[cnt++] = u;
            for (int j = 0; j < n; j++)
                if (map[u][j] == 1)
                    if (--indegree[j] == 0)
                        s.push(j);
        }
        if (cnt < n) {
            return false;
        }
        return true;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
 
        for (int i = 0; i < m; i++) {
            int u, v;
            u = scanner.nextInt();
            v = scanner.nextInt();
            map[u][v] = 1;
            indegree[v]++;
        }
        TopoSort();
        for (int i = 0; i < n - 1; i++)
            System.out.print(topo[i] + " ");
        System.out.println(topo[n - 1]);
    }
}