浙江大學-數據結構-拓撲序列-8.2.1

拓撲排序

課的順序不是隨便亂修的，當課的數量大大增多的時候，就變成了相當複雜的事情，數據結構中的什麼工具可以用來被解決這個問題呢？我們這一章是講的圖，所以我們肯定得用一個圖來解決這個問題，要描述一個圖，要搞清楚兩件事情，一個什麼是它的頂點，那在這裡頭好像比較好想，比如說我就把每一門課當成是圖裡面的每一個頂點就好了，然後第二個問題就是，什麼是邊呢？在這個問題裡面，這個邊是有向邊，如果從一個頂點到另一個頂點，就是從一門課到另一門課有一條邊的話，就意味著前面的這門課是後面這門課的預修課程，如果它們之間有預修課程關係的話，它們之間就會有一條邊，就對這個例子，我們的圖要怎麼畫出來呢？首先我們看一看有哪些課程是沒有預修課程的，先把這4個頂點畫出來。

這樣就完成了課程的依賴關係圖，那這種圖有個名字叫AOV網路，也就是說在這個有向圖裡面所有真實的活動是表現在頂點上的。

那頂點和頂點之間有向邊表示了兩個活動之間的活動順序，那我們把整個問題抽象一下，就抽象成一個拓撲排序的問題，

什麼叫合理的拓撲序呢？就是如果這個圖裡面居然有一個環的話，它意味著什麼呢？就意味著V這個活動，它自己是它自己的前驅結點，也就意味著，它在它自己開始之前，它必須要已經結束了，所以V必須在V開始之前結束，這是一個不可能的事情

所以如果這個有向圖裡存在環，那麼它一定就不可能得到一個合理的拓撲序

又回到剛才這個排序的問題，假如說我們給了這麼一個AOV網路，那麼根據這個網路我要怎麼把這個課程的順序排出來呢？用一下常識性的思維，首先第一學期可以排哪些課呢？肯定是排那些沒有預修課程的課，這4個頂點，也就是C1,C2,C8,C4這4門課都是沒有預修課程的，所以我就可以直接把它輸出，先輸出哪個，後輸出哪個，這倒是無所謂的，隨便挑一個就好了，比如說我把C1來輸出，輸出的同時我就把C1從圖裡面給抹掉了

什麼叫抹掉呢？不僅是抹掉這個頂點，我最重要的是抹掉這條邊

抹掉這條邊以後，我們再檢查剩下的圖，我們仍然有3個，隨便再輸出一個，把C2輸出，C2輸出以後我們發現這圖變成什麼樣子了呢？

除了C4,C8是沒有預修課程之外，C3和C13也沒有預修課程了，那我是不是可以直接把C3和C13先輸出了呢？也不是完全不可以，但是不太好，為什麼不太好呢？總之在這，我不選擇這兩個頂點，雖然我可以這麼做，我仍然繼續選擇把C8輸出，

然後把C4在輸出，這樣的話，4門課我把它排在第一個學期上掉，是不會產生任何矛盾的，然後第二個學期我要開始排，怎麼排呢？我看一下現在圖裡面，我要有這麼4門課，它是沒有前驅結點的，

於是我再把它們一個一個的抹掉，輸出

那再下來呢，我會看到再下個學期會排C7和C6了，於是把C7，C6輸出

再下一個學期呢，C12,C10,C11,C15都是可以的，我再把它們依次的輸出來，最後一個學期呢，我可以排C14,這樣就完成了一個排課的過程。

這個過程實際上就是一個拓撲排序的過程，它的規律是什麼？大家有沒有注意到，就是每一次我們要輸出哪個頂點呢，我們要輸出的是沒有前驅頂點的那個頂點，我怎麼知道它沒有前驅頂點呢？我們知道對於一個有向圖來說，每個頂點我們有兩個度可以記的，一個是它的入度，一個是它的出度，所謂沒有前驅頂點那些課程，它們的特點是什麼，就是它們的入度都是0，沒有任何一條邊指向它，所以它的入度為0，每次我們選擇的都是入度為0的那個頂點，在輸出的同時，我們要把這個頂點從原始的圖裡面徹底抹掉，當我們把原來的圖抹光的時候，一個正常的拓撲序就產生了，

這個就是我們拓撲排序的演算法，

這個程序的框架很簡單，我們是要把所有的頂點一個一個輸出，前面設置了cnt,做了一個for循環，你願意把它做成while循環，都可以，每一次循環裡面我們要找一個還沒有被輸出的並且入度為0的頂點，找到它以後，我就把它輸出來，或者記錄一下輸出序號，然後我要把這個V從原圖裡面抹掉，什麼是抹掉呢？我不是真的把這個V刪掉，而是說把V的每個鄰接點它的入度減1，就意味著我把從V到W的這條邊給減掉了。W少了一條進來的邊，所以它相應的Indegree就會減1，如果我們每一步的執行都是正常的，一直到這個cnt等於V-1的時候，就是整個這個外循環執行了V步的時候，我們當然也就自然的把所有的頂點都輸出了，但是如果外循環還沒有結束，在這一步我就已經找不到滿足這個條件的V了(V = 未輸出的入度為0的頂點),那說明什麼問題呢？如果外循環還沒有結束，而這樣的V就已經不存在了

就意味著這個圖裡面還剩下好幾個頂點沒有被輸出，但是每一個頂點入度都不是0，每一個頂點都有一個邊指向它，那麼這種情況下，圖中必定是有一個迴路的，也就是說，這個AOV不是一個合理的AOV，這件事情整個是不可能的，那麼我們就不往下做了，整個break，跳出來，這就是一個簡單的拓撲排序的演算法。當然它整體的時間複雜度，就很大程度上依賴於說這一步(V = 未輸出的入度為0的頂點)到底是怎麼找的，如果我用簡單粗暴的方法，就是把所有的點都掃描一遍，然後去找那個又沒有輸出過的，然後入度又為0的頂點，這時候這一步的做法如果是O(|V|)這個複雜度的話，那我們整體的時間複雜度顯然就是O(|V|^2)，這個其實是一種非常不聰明的做法，

聰明的做法是什麼樣子的呢？聰明的做法是讓（V = 未輸出的入度為0的頂點)加快，其實這個聰明的解決方案也非常的直接了當，我們隨時檢查當任何一個頂點它的入度變為0的時候，我不要把它還放在老地方，

我把它放到一個特殊的容器里，這個容器呢，你可以把它理解為任何東西，你可以把它另外放到一個數組裡，另外放到一個鏈表裡，另外放到一個堆棧里，還是放到一個隊列里，這個容器你怎麼定義它都可以，總之你把它放到一個特殊的地方，所以當下一次我要找一個度為0的頂點的時候，我就不用去掃描所有的頂點集合了，我直接到這個容器里去取一個出來就好了，所所以這個時間複雜度就頓時變成一個常數級的時間複雜度，

假設我在這裡頭我用一個隊列做這個容器，拓撲排序就變成了這個樣子，首先第一步我要先檢查圖裡面的每一個頂點V，有沒有入度為0的，如果入度為0的話，我通通把它放到這個容器裡面去(Enqueue(V, Q)),然後我就開始不斷的檢查這個容器了，每次從這個容器裡面取出一個頂點，這個頂點必然是入度為0的頂點(V = Dequeue(Q)),那我就把它直接輸出，輸出完了以後，我要把這個頂點從這個圖裡抹掉，就意味著我要把它的每個鄰接點的入度都要減1，在減1的同時，我要去檢查一下它是不是減完了入度就為0了，

如果它減完了以後，入度為0，我就把它放到這個容器裡面(if (--Indegree[W] == 0) Enqueue(W, Q)),下一次可以取出來用，否則的話就什麼都不做，繼續去容器里取下一個頂點，那麼當我從這個while循環里跳出來，什麼條件下我就知道這個圖中一定是有迴路的呢？如果我從這個while循環裡面跳出來的時候，並不是所有的頂點都已經被輸出了，就還有頂點留在圖裡，那麼就意味著這個圖裡面一定是有迴路的了，那我怎麼知道輸出了多少個頂點呢？很簡單的，我輸出的時候我在這加一個計數器(cnt++),

每次給它加加一下，然後出來的時候，我就數一下這個計數器正常情況下應該等於頂點的個數，如果不相等的話，那麼圖中一定有迴路，那麼我們把演算法改成這個樣子以後，

時間複雜度是多少呢？就很簡單了，每一個頂點會入列一次，然後因為我檢查了V的每個鄰接點，所以每條邊也被掃描了一次，所以總體的時間複雜度就變成了O(|V|+|E|),如果它是稀疏圖的話呢，這差不多是一個O(|V|)的時間複雜度，如果它是稠密圖的話呢，它也就是O(|V|^2)這個數量級的，這個演算法還可以用來檢測一個有向圖是不是一個有向無環圖，是不是一個DAG