什么是拓?fù)渑判颍?/h1>

維基百科對于拓?fù)渑判蛴腥缦露x：

a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

即：對于任何有向圖而言雀久，其拓?fù)渑判驗(yàn)槠渌薪Y(jié)點(diǎn)的一個線性排序（對于同一個有向圖而言可能存在多個這樣的結(jié)點(diǎn)排序）。該排序滿足這樣的條件——對于圖中的任意兩個結(jié)點(diǎn)u和v，若存在一條有向邊從u指向v，則在拓?fù)渑判蛑?em>u一定出現(xiàn)在v前面沐寺。

拓?fù)渑判蛑饕脕斫鉀Q有向圖中的依賴解析（dependency resolution）問題。

舉例來說媚朦，如果我們將一系列需要運(yùn)行的任務(wù)構(gòu)成一個有向圖尸折，圖中的有向邊則代表某一任務(wù)必須在另一個任務(wù)之前完成這一限制。那么運(yùn)用拓?fù)渑判蚯烀幔覀兙湍艿玫綕M足執(zhí)行順序限制條件的一系列任務(wù)所需執(zhí)行的先后順序康吵。當(dāng)然也有可能圖中并不存在這樣一個拓?fù)漤樞颍@種情況下我們無法根據(jù)給定要求完成這一系列任務(wù)访递，這種情況稱為循環(huán)依賴（circular dependency）晦嵌。

拓?fù)渑判虼嬖诘那疤?/h1>

當(dāng)且僅當(dāng)一個有向圖為有向無環(huán)圖（directed acyclic graph，或稱DAG）時(shí)拷姿，才能得到對應(yīng)于該圖的拓?fù)渑判虿言亍Ｃ恳粋€有向無環(huán)圖都至少存在一種拓?fù)渑判颉Ｔ撜摂嗫梢岳梅醋C法被證明如下：

假設(shè)我們有一由v_1到v_n這n個結(jié)點(diǎn)構(gòu)成的有向圖响巢，且圖中v_1描滔，v_2，...踪古，v_n這些結(jié)點(diǎn)構(gòu)成一個環(huán)含长。這即是說對于所有1≤i<n-1，圖中存在一條有向邊從v_i指向v_i+1伏穆。同時(shí)還存在一條從v_n指向v_1的邊拘泞。假設(shè)該圖存在一個拓?fù)渑判颉?/p>

那么基于這樣一個有向圖，顯然我們可以得知對于所有1≤i<n-1枕扫，v_i必須在v_i+1之前被遍歷陪腌，也就是v_1必須在v_n之前被遍歷。同時(shí)由于還存在一條從v_n指向v_1的邊，v_n必須在v_1之前被遍歷诗鸭。這里出現(xiàn)了與我們的假設(shè)所沖突的結(jié)果商叹。因此我們可以知道，該圖存在拓?fù)渑判虻募僭O(shè)不成立只泼。也就是說剖笙，對于非有向無環(huán)圖而言，其拓?fù)渑判虿淮嬖凇?/p>

拓?fù)渑判虻乃惴ê蛯?shí)現(xiàn)

拓?fù)渑判虻膯栴}存在一個線性時(shí)間解请唱。也就是說弥咪，若有向圖中存在n個結(jié)點(diǎn)，則我們可以在O(n)時(shí)間內(nèi)得到其拓?fù)渑判蚴螅蛟?code>O(n)時(shí)間內(nèi)確定該圖不是有向無環(huán)圖聚至，也就是說對應(yīng)的拓?fù)渑判虿淮嬖凇?/p>

例如一個有向無環(huán)圖如下：

DAG1

根據(jù)圖中的邊的方向，我們可以看出本橙，若要滿足得到其拓?fù)渑判虬夤瑒t結(jié)點(diǎn)被遍歷的順序必須滿足如下要求：

1. 結(jié)點(diǎn)1必須在結(jié)點(diǎn)2、3之前
2. 結(jié)點(diǎn)2必須在結(jié)點(diǎn)3甚亭、4之前
3. 結(jié)點(diǎn)3必須在結(jié)點(diǎn)4贷币、5之前
4. 結(jié)點(diǎn)4必須在結(jié)點(diǎn)5之前

則一個滿足條件的拓?fù)渑判驗(yàn)?code>[1, 2, 3, 4, 5]。

若我們刪去圖中4亏狰、5結(jié)點(diǎn)之前的有向邊役纹，上圖變?yōu)槿缦滤荆?/p>

DAG2

則我們可得到兩個不同的拓?fù)渑判蚪Y(jié)果：[1, 2, 3, 4, 5]和[1, 2, 3, 5, 4]。

為了說明如何得到一個有向無環(huán)圖的拓?fù)渑判蛳就伲覀兪紫刃枰私庥邢驁D結(jié)點(diǎn)的入度（indegree）和出度（outdegree）的概念促脉。

假設(shè)有向圖中不存在起點(diǎn)和終點(diǎn)為同一結(jié)點(diǎn)的有向邊。

入度：設(shè)有向圖中有一結(jié)點(diǎn)v策州，其入度即為當(dāng)前所有從其他結(jié)點(diǎn)出發(fā)瘸味，終點(diǎn)為v的的邊的數(shù)目。也就是所有指向v的有向邊的數(shù)目够挂。

出度：設(shè)有向圖中有一結(jié)點(diǎn)v旁仿，其出度即為當(dāng)前所有起點(diǎn)為v，指向其他結(jié)點(diǎn)的邊的數(shù)目下硕。也就是所有由v發(fā)出的邊的數(shù)目丁逝。

在了解了入度和出度的概念之后汁胆，再根據(jù)拓?fù)渑判虻亩x梭姓，我們自然就能夠得出結(jié)論：要想完成拓?fù)渑判颍覀兠看味紤?yīng)當(dāng)從入度為0的結(jié)點(diǎn)開始遍歷嫩码。因?yàn)橹挥腥攵葹?的結(jié)點(diǎn)才能夠成為拓?fù)渑判虻钠瘘c(diǎn)誉尖。否則根據(jù)拓?fù)渑判虻亩x，只要一個結(jié)點(diǎn)v的入度不為0铸题，則至少有一條邊起始于其他結(jié)點(diǎn)而指向v铡恕，那么這條邊的起點(diǎn)在拓?fù)渑判虻捻樞蛑袘?yīng)當(dāng)位于v之前琢感，則v不能成為當(dāng)前遍歷的起點(diǎn)。

由此我們可以進(jìn)一步得出一個改進(jìn)的深度優(yōu)先遍歷或廣度優(yōu)先遍歷算法來完成拓?fù)渑判蛱饺邸Ｒ詮V度優(yōu)先遍歷為例驹针，這一改進(jìn)后的算法與普通的廣度優(yōu)先遍歷唯一的區(qū)別在于我們應(yīng)當(dāng)保存每一個結(jié)點(diǎn)對應(yīng)的入度，并在遍歷的每一層選取入度為0的結(jié)點(diǎn)開始遍歷（而普通的廣度優(yōu)先遍歷則無此限制诀艰，可以從該吃呢個任意一個結(jié)點(diǎn)開始遍歷）柬甥。這個算法描述如下：

1. 初始化一個int[] inDegree保存每一個結(jié)點(diǎn)的入度。
2. 對于圖中的每一個結(jié)點(diǎn)的子結(jié)點(diǎn)其垄，將其子結(jié)點(diǎn)的入度加1苛蒲。
3. 選取入度為0的結(jié)點(diǎn)開始遍歷，并將該節(jié)點(diǎn)加入輸出绿满。
4. 對于遍歷過的每個結(jié)點(diǎn)臂外，更新其子結(jié)點(diǎn)的入度：將子結(jié)點(diǎn)的入度減1。
5. 重復(fù)步驟3喇颁，直到遍歷完所有的結(jié)點(diǎn)漏健。
6. 如果無法遍歷完所有的結(jié)點(diǎn)，則意味著當(dāng)前的圖不是有向無環(huán)圖橘霎。不存在拓?fù)渑判颉?/li>

廣度優(yōu)先遍歷拓?fù)渑判虻腏ava代碼如下漾肮。

public class TopologicalSort {
    /**
     * Get topological ordering of the input directed graph 
     * @param n number of nodes in the graph
     * @param adjacencyList adjacency list representation of the input directed graph
     * @return topological ordering of the graph stored in an List<Integer>. 
     */
    public List<Integer> topologicalSort(int n, int[][] adjacencyList) {
        List<Integer> topoRes = new ArrayList<>();
        int[] inDegree = new int[n];
        for (int[] parent : adjacencyList) {
            for (int child : parent) {
                inDegree[child]++;
            }
        }
        
        Deque<Integer> deque = new ArrayDeque<>();
        
        // start from nodes whose indegree are 0
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) deque.offer(i);
        }
        
        while (!deque.isEmpty()) {
            int curr = deque.poll();
            topoRes.add(curr);
            for (int child : adjacencyList[curr]) {
                inDegree[child]--;
                if (inDegree[child] == 0) {
                    deque.offer(child);
                }
            }
        }
    
        return topoRes.size() == n ? topoRes : new ArrayList<>();
    }
}

時(shí)間復(fù)雜度： O(n + e)，其中n為圖中的結(jié)點(diǎn)數(shù)目茎毁，e為圖中的邊的數(shù)目

空間復(fù)雜度：O(n)

典型應(yīng)用：

Leetcode 210. Course Schedule II