對一個有向無環圖（Directed Acyclic Graph簡稱DAG）G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊（u，v）∈E（G），則u在線性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序（Topological Order）的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
預備知識
一個較大的工程往往被劃分成許多子工程，我們把這些子工程稱作活動（activity）。在整個工程中，有些子工程（活動）必須在其它有關子工程完成之后才能開始，也就是說，一個子工程的開始是以它的所有前序子工程的結束為先決條件的，但有些子工程沒有先決條件，可以安排在任何時間開始。為了形象地反映出整個工程中各個子工程（活動）之間的先后關系，可用一個有向圖來表示，圖中的頂點代表活動（子工程），圖中的有向邊代表活動的先后關系，即有向邊的起點的活動是終點活動的前序活動，只有當起點活動完成之后，其終點活動才能進行。通常，我們把這種頂點表示活動、邊表示活動間先后關系的有向圖稱做頂點活動網（Activity On Vertex network），簡稱 AOV網。
例如，假定一個計算機專業的學生必須完成圖3-4所列出的全部課程。在這里，課程代表活動，學習一門課程就表示進行一項活動，學習每門課程的先決條件是學完它的全部先修課程。如學習《數據結構》課程就必須安排在學完它的兩門先修課程《離散數學》和《算法語言》之后。學習《高等數學》課程則可以隨時安排，因為它是基礎課程，沒有先修課。若用AOV網來表示這種課程安排的先后關系，則如圖3-5所示。圖中的每個頂點代表一門課程，每條有向邊代表起點對應的課程是終點對應課程的先修課。從圖中可以清楚地看出各課程之間的先修和后續的關系。如課程C5的先修課為C2，后續課程為C4和C6。
一個AOV網應該是一個有向無環圖，即不應該帶有回路，因為若帶有回路，則回路上的所有活動都無法進行。如圖3-6是一個具有三個頂點的回路，由
在AOV網中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅活動都排在該活動的前面，我們把此序列叫做拓撲序列（Topological order），由AOV網構造拓撲序列的過程叫做拓撲排序（Topological sort）。AOV網的拓撲序列不是唯一的，滿足上述定義的任一線性序列都稱作它的拓撲序列。
由AOV網構造出拓撲序列的實際意義是：如果按照拓撲序列中的頂點次序，在開始每一項活動時，能夠保證它的所有前驅活動都已完成，從而使整個工程順序進行，不會出現沖突的情況。
執行步驟
由AOV網構造拓撲序列的拓撲排序算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止。
（1）選擇一個入度為0的頂點并輸出之；
（2）從網中刪除此頂點及所有出邊。
循環結束后，若輸出的頂點數小于網中的頂點數，則輸出“有回路”信息，否則輸出的頂點序列就是一種拓撲序列。
非計算機應用
拓撲排序常用來確定一個依賴關系集中，事物發生的順序。例如，在日常工作中，可能會將項目拆分成A、B、C、D四個子部分來完成，但A依賴于B和D，C依賴于D。為了計算這個項目進行的順序，可對這個關系集進行拓撲排序，得出一個線性的序列，則排在前面的任務就是需要先完成的任務。
注意：這里得到的排序并不是唯一的！就好像你早上穿衣服可以先穿上衣也可以先穿褲子，只要里面的衣服在外面的衣服之前穿就行。
應用
拓撲序列Pascal代碼（無優化）
拓撲序列C++（STL）核心代碼
這里的代碼可以參考這本書，這里是我自己敲的代碼，用了容器，感覺能看明白點。
拓撲序列Pascal代碼（鄰接表+隊列優化）
這里主要是將入度為零的點加入隊列stack，直接在隊列內擴展即可，效率為O（n+m）
拓撲學
拓撲學是近代發展起來的一個研究連續性現象的數學分支。中文名稱起源于希臘語Τοπολογ?α的音譯。Topology原意為地貌，于19世紀中期由科學家引入，當時主要研究的是出于數學分析的需要而產生的一些幾何問題。發展至今，拓撲學主要研究拓撲空間在拓撲變換下的不變性質和不變量。
參考資料 >
拓撲排序.cnblog.2014-08-24