拓撲排序

對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u線上性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。

基本介紹

• 中文名：拓撲排序
• 外文名：topological-sort
• 別稱：toposort topsort
• 套用學科：計算機科學 圖論 

預備知識

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

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

圖3-5 這種先後關係的AOV網

一個AOV網應該是一個有向無環圖，即不應該帶有迴路，因為若帶有迴路，則迴路上的所有活動都無法進行。如圖3-6是一個具有三個頂點的迴路，由<A,B>邊可得B活動必須在A活動之後，由<B,C>邊可得C活動必須在B活動之後，所以推出C活動必然在A活動之後，但由<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;varmap,link:array[1..100,1..100]ofinteger;v,pnt:array[1..100]ofinteger;n,m,a,b,i,j,k:integer;beginfillchar(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<n) do 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 begindec(v[k]);link[j,k]:=0;end;inc(i);pnt[i]:=j;end;fori:=1 to n doln(pnt[i]);end.

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

這裡的代碼可以參考這本書，這裡是我自己敲的代碼，用了容器，感覺能看明白點。

queue<int>q;//priority_queue<int,vector<int>,greater<int>>q;//優先佇列的話，會按照數值大小有順序的輸出//此處為了理解，暫時就用簡單佇列inttopo(){    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=recordprocedure 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)

拓撲學

拓撲學是近代發展起來的一個研究連續性現象的數學分支。中文名稱起源於希臘語Τοπολογία的音譯。Topology原意為地貌，於19世紀中期由科學家引入，當時主要研究的是出於數學分析的需要而產生的一些幾何問題。發展至今，拓撲學主要研究拓撲空間在拓撲變換下的不變性質和不變數。