在前面的課程中，講述了圖的兩種基本表示方法：鄰接表和鄰接矩陣片排，以及兩種基本的遍歷：廣度遍歷和深度遍歷寨腔。在此基礎上，我們一起探討圖的第一個基本的應用：拓撲排序率寡。
什么叫拓撲排序迫卢？請大家先看下面的一張圖：
所謂拓撲排序，就是根據(jù)有向圖中的偏序關系冶共，對圖中的節(jié)點進行排序乾蛤。對于圖1中的例子而言，排課老師的任務是：根據(jù)課程之間的先修關系比默，每個學期合理安排課程幻捏，保證每門課的先修課都必須安排在這門課的前面盆犁。如果是你命咐，你如何排？
在進一步思考之前谐岁，首先應該明白醋奠，只有有向無環(huán)圖才有拓撲排序榛臼，無向圖和有環(huán)的有向圖都不可能有拓撲排序。
在沒有學習圖論之前窜司，大家的想法可能是：先找到所有入度為0的節(jié)點沛善，然后順著這些節(jié)點繼續(xù)尋找，但是順著這些節(jié)點后面的尋找規(guī)則是什么塞祈？如C9的入度為0金刁，順著C9，有C10议薪、C11和C12尤蛮，這三者又是什么關系呢？進一步斯议，可以發(fā)現(xiàn)C10是C12的先修課程产捞，也就是拓撲排序中，C9必須安排在C10之前哼御，C10必須安排在C12之前坯临。但是到現(xiàn)在為止，我們并未明確表述這些規(guī)則是什么恋昼？
拓撲排序的根本目的是：根據(jù)圖節(jié)點之間的偏序關系看靠，對圖進行排序。偏序關系在有向圖中的表現(xiàn)就是有向邊液肌，再進一步衷笋，我們可以看作是在圖的遍歷過程中對其進行排序【仄ǎ考慮前面課程中學習的廣度遍歷和深度遍歷辟宗，廣度遍歷是對外逐層擴展，主要用于求源節(jié)點到所有其它節(jié)點的最短路徑吝秕，體現(xiàn)的是距離泊脐；深度遍歷則是對當前節(jié)點，依據(jù)有向邊對當前的鄰接節(jié)點繼續(xù)深入遍歷烁峭，整個遍歷過程其實質(zhì)就體現(xiàn)了拓撲排序中的關系容客。
以C9、C10约郁、C11缩挑、C12為例，對其拓撲排序的可能包括(三種典型的鬓梅，還有其它類似幾種可能)：
- C9(1/12) -> C10(2/5) -> C12(3/4) -> C11(6/11) -> C6(7/10) -> C8(8/9)
- C9(1/12) -> C12(2/3) -> C10(4/5) -> C11(6/11) -> C6(7/10) -> C8(8/9)
- C9(1/12) -> C11(2/7) -> C6(3/6) -> C8(4/5) -> C12(8/9) -> C10(10/11)
上面列出的節(jié)點中的括號中的數(shù)據(jù)C9(m/n)供置，m表示發(fā)現(xiàn)節(jié)點的時間，n表示當前節(jié)點的所有鄰接節(jié)點已全部發(fā)現(xiàn)的完成時間（忘記的童鞋請查閱：前面課程）绽快，如果按照完成時間倒排會是什么芥丧？上面的三種的排列結(jié)果分別為：
- C9, C11, C6, C8, C10, C12
- C9, C11, C6, C8, C10, C12
- C9, C10, C12, C11, C6, C8
仔細觀察紧阔，上面的排序結(jié)果均滿足前文提到的先修關系（提示：拓撲排序可能不止一種），即：深度遍歷的完成時間倒排序即是拓撲排序結(jié)果续担，下面對其進行分析證明：
分析：假設圖G(V, E)擅耽，對于圖中任意節(jié)點v，v.d表示發(fā)現(xiàn)節(jié)點v的時間物遇，v.f表示v的所有鄰接節(jié)點遍歷完成的時間, 若有（u, v）是E中的一條邊乖仇，只需要證明v.f < u.f。 對E中的任意邊（u, v）询兴，在深度遍歷中这敬，當通過u對v進行探索時，v肯定不是灰色（如果v是灰色蕉朵，則表示v的鄰接節(jié)點深度遍歷還未結(jié)束崔涂，u肯定是v的后繼節(jié)點，則u和v構成了環(huán)始衅，這種情況下冷蚂，不可能存在拓撲排序），如果v是白色汛闸，則必然有v.f < u.f成立蝙茶；如果v是黑色，則表示v的鄰接節(jié)點已經(jīng)遍歷完成诸老，v.f < u.f顯然成立隆夯。由此：結(jié)論成立。（注意：深度遍歷中别伏，節(jié)點v為白色表示還未發(fā)現(xiàn)v蹄衷，為灰色表示v被發(fā)現(xiàn)，并開始訪問其鄰接節(jié)點厘肮，為黑色表示v的所有鄰接節(jié)點已訪問完畢愧口，結(jié)束v的訪問）
因此，圖的深度遍歷中記錄的遍歷訪問結(jié)束時間就是拓撲排序的依據(jù)类茂，當然耍属，其原理其實也很簡單，童鞋們只需仔細把這個證明分析推敲一遍就形了巩检。相應的源代碼請見（ https://github.com/bjutJohnson/Algorithms/blob/master/src/graph/graph_manager.go ）中的TopologySort函數(shù)厚骗。
