拓撲排序:計算機術語-中文百科頻道

預備知識

一個較大的工程往往被劃分成許多子工程，我們把這些子工程稱作活動(activity)。在整個工程中，有些子工程(活動)必須在其它有關子工程完成之後才能開始，也就是說，一個子工程的開始是以它的所有前序子工程的結束為先決條件的，但有些子工程沒有先決條件，可以安排在任何時間開始。為了形象地反映出整個工程中各個子工程(活動)之間的先後關系，可用一個有向圖來表示，圖中的頂點代表活動(子工程)，圖中的有向邊代表活動的先後關系，即有向邊的起點的活動是終點活動的前序活動，隻有當起點活動完成之後，其終點活動才能進行。通常，我們把這種頂點表示活動、邊表示活動間先後關系的有向圖稱做頂點活動網(Activity On Vertex network)，簡稱AOV網。

例如，假定一個計算機專業的學生必須完成圖3-4所列出的全部課程。在這裡，課程代表活動，學習一門課程就表示進行一項活動，學習每門課程的先決條件是學完它的全部先修課程。如學習《數據結構》課程就必須安排在學完它的兩門先修課程《離散數學》和《算法語言》之後。學習《高等數學》課程則可以随時安排，因為它是基礎課程，沒有先修課。若用AOV網來表示這種課程安排的先後關系，則如圖3-5所示。圖中的每個頂點代表一門課程，每條有向邊代表起點對應的課程是終點對應課程的先修課。從圖中可以清楚地看出各課程之間的先修和後續的關系。如課程C5的先修課為C2，後續課程為C4和C6。

一個AOV網應該是一個有向無環圖，即不應該帶有回路，因為若帶有回路，則回路上的所有活動都無法進行。如圖3-6是一個具有三個頂點的回路，由邊可得B活動必須在A活動之後，由邊可得C活動必須在B活動之後，所以推出C活動必然在A活動之後，但由邊可得C活動必須在A活動之前，從而出現矛盾，使每一項活動都無法進行。這種情況若在程序中出現，則稱為死鎖或死循環，是必須避免的。

在AOV網中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅活動都排在該活動的前面，我們把此序列叫做拓撲序列(Topological order)，由AOV網構造拓撲序列的過程叫做拓撲排序(Topological sort)。AOV網的拓撲序列不是唯一的，滿足上述定義的任一線性序列都稱作它的拓撲序列。

由AOV網構造出拓撲序列的實際意義是：如果按照拓撲序列中的頂點次序，在開始每一項活動時，能夠保證它的所有前驅活動都已完成，從而使整個工程順序進行，不會出現沖突的情況。

執行步驟

由AOV網構造拓撲序列的拓撲排序算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止。

(1) 選擇一個入度為0的頂點并輸出之；

(2) 從網中删除此頂點及所有出邊。

循環結束後，若輸出的頂點數小于網中的頂點數，則輸出“有回路”信息，否則輸出的頂點序列就是一種拓撲序列。

非計算機應用

拓撲排序常用來确定一個依賴關系集中，事物發生的順序。例如，在日常工作中，可能會将項目拆分成A、B、C、D四個子部分來完成，但A依賴于B和D，C依賴于D。為了計算這個項目進行的順序，可對這個關系集進行拓撲排序，得出一個線性的序列，則排在前面的任務就是需要先完成的任務。

注意：這裡得到的排序并不是唯一的！就好像你早上穿衣服可以先穿上衣也可以先穿褲子，隻要裡面的衣服在外面的衣服之前穿就行。

應用

拓撲序列 Pascal代碼（無優化）

program TopSort;var map,link:array[1..100,1..100]ofinteger; v,pnt:array[1..100]ofinteger; n,m,a,b,i,j,k:integer;begin fillchar(map,sizeof(map),0); fillchar(link,sizeof(link),0); fillchar(v,sizeof(v),0); //初始化 readln(n,m); for i:=1 to m do begin //讀圖 readln(a,b); map[a,b]:=1; v[b]:=v[b]+1; end; i:=0; link:=map; while (i begin //開始排序 j:=1; while (v[j]<>0) do inc(j); v[j]:=-1; for k:=1 to n do if link[j,k]=1 then begin dec(v[k]); link[j,k]:=0; end; inc(i); pnt[i]:=j; end; for i:=1 to n do writeln(pnt[i]);end.

拓撲序列 C++（STL）核心代碼

這裡的代碼可以參考這本書 [3] ，這裡用了容器，感覺能看明白點。

queueq;//priority_queue,greater>q;//優先隊列的話，會按照數值大小有順序的輸出//此處為了理解，暫時就用簡單隊列int topo(){ for(inti=1;i<=n;i++) { if(indegree[i]==0) { q.push(i); } } int temp; while(!q.empty()) { temp=q.front();//如果是優先隊列，這裡可以是top() printf("%d->",temp); q.pop(); for(inti=1;i<=n;i++)//遍曆從temp出發的每一條邊，入度-- { if(map[temp][i]) { indegree[i]--; if(indegree[i]==0)q.push(i); } } }}

拓撲序列 Pascal代碼（鄰接表+隊列優化）

program topsort;typenode=^link;link=record procedure addd(x,y:longint);var p:node;beginnew(p);p^.g:=y;p^.next:=nd[x];nd[x]:=p;inc(ru[y]);end;beginreadln(n,m);for a:=1 to m dobeginreadln(x,y);addd(x,y);end;for a:=1 to n doif ru[a]=0 then begininc(stk);stack[stk]:=a;end;be:=0;repeatinc(be);x:=stack[be];p:=nd[x];write(x,'');while p<>nil dobegindec(ru[p^.g]);if ru[p^.g]=0 then begininc(stk);stack[stk]:=p^.g;end;p:=p^.next;end;until be=stk;readln;end.

這裡主要是将入度為零的點加入隊列stack，直接在隊列内擴展即可，效率為O(n+m)