有向無環圖(DAG)的所有拓撲序列

拓撲序列:

當一個有向圖無環時，會存在拓撲序列。即将有向圖G中的頂點按照線性序列排列，使得G中的任意兩個頂點u和v ,使得 for (u,v) in Edges(G), 線上性序列中都滿足u出現在v的前面。

求一個DAG的一條拓撲序列很好求，隻要按照如下步驟即可：

1.       找到目前所有的無直接前驅的vertex(未曾通路過)，若沒有這樣的頂點，跳到3。若有，從中選一個v，标記為已通路，加入到目前序列的尾部，繼續2。

2.       将從v出發的有向邊全部删除(這樣會得到一個新的有向圖G’)。

3.       如果序列中的頂點數不等于有向圖G的頂點個數，則說明圖G中存在環；如果相等，則該序列即是所求的拓撲序列。

現在要求有向圖G的所有拓撲序列。

可采用回溯法。

先看個小例子：

有三個集合A，B，C，每個集合中都有若幹個頂點，要求從三個集合中依次(先從A再B最後從C)取出一個頂點，組成一個序列，問這樣的序列有多少。

假設A={v1, v2, v3}   B={v4, v5}  C={v6, v7, v9}

顯然有3*2*3=18種這種序列。

即: v1->v4->v6   v1->v4->v7   v1->v4->v9   v1->v5->v6  v1->v5->v7  …  v3->v5->v9

自然通過回溯很好将這些序列全部輸出:

Index[3] = {0};

data[0] = {v1, v2, v3}

data[1]={v4, v5}

data[2]={v6, v7, v8}

length[3]={3,2,3}

result[3];

i= 0;

while(i>=0)

{

         If(i<3)   //繼續向下搜尋解,3代表欲求序列的長度

         {

                   If(index[i] < length[i])   //還有可能的取值, index[i]表示目前可能取值的下标

                   {

                            result[i]=data[i][ index[i] ];

                            index[i]++;

                            i++;

                   }

                   else   //無可能的取值了，回溯

                   {

                            tmp = i;

                            i--;

                            while(tmp <3) //将後面的可能取值的索引下标都置為初始值0, 使得回溯到前一個後，後面重新開始

                                     index[tmp++]=0;

                   }

         }

         else

         {

                   //得到一個解了

                   Print(result)

                   i--;  //再回溯回去，繼續求解

         }

}

此處我們求所有拓撲序列也可以用回溯的方法。

每當我們執行上述求單一拓撲序列的第一步時，我們得到一個頂點集合S，我們在每個集合裡面都設個索引标記index，表示目前我取得是集合裡面的第幾個頂點，這樣就可以跟上例一樣，通過index來取頂點&&判斷目前集合中的頂點是否都已經用過了。

假設有向圖G的頂點個數為V，則我們的拓撲序列的元素個數也應該是V，我們用result[V]來存放目前的拓撲序列。假設我們目前正在處理第i個拓撲序列中的元素result[i]

執行步驟如下：

1.       求目前有向圖中所有無直接前驅的頂點集合S(i)，設屬于集合的索引index=0，如果集合非空，則跳轉到2,；如果集合為空，則跳轉到3.

2.       如果index<length(S(i))，取S(i)[index]作為目前序列元素result[i]的值，并且将index增1，将從頂點result[i]出去的有向邊全部從有向圖中去掉，但是将去掉的有向邊全部記錄下來(等回溯的時候恢複).再接着求序列的下一個元素result[i+1]的值，跳轉到1繼續執行。

如果index>length(S(i))，即index的值如果大于集合S(i)的大小了，說明目前集合S(i)中的值都用過了，必須回溯到前一個序列元素result[i-1]，将它的值變成它對應集合(S(i-1))中的下一個可能的值.假設之前result[i-1]使用的是S(i-1)[n]，那麼現在result[i-1]就應該使用s(i-1)[n+1]了,然後繼續向後搜尋(繼續執行1)，當然在使用該值之前需要将之前删除的以s(i-1)[n]為出發點的有向邊全部恢複，自然如果這裡的n的大小已經等于S(i-1)中元素的個數了，那麼序列繼續回溯：i減1，并且恢複删除的邊，嘗試新的取值。當i回溯到-1，求值過程也就結束了

3.       如果目前序列中的元素個數等于V，說明已經求得了一個拓撲序列，輸出，然後回溯,嘗試着繼續求其他可能的拓撲序列。

這題好似資料結構的學期課程設計題之一。

有種做法很二筆，先求所有頂點的排序序列，在得到一個序列後再判斷這個序列是否是有向無環圖的一個拓撲序列，這個時間是指數級的。這個方法很好，不過這個方法的編碼實作也不是那麼好搞，具體代碼下載下傳：http://download.csdn.net/download/peibaoyi/5744269

代碼中的頂點從0開始編号，邊是通過頂點的編号來指定的.