拓?fù)渑判蚓褪菍⒂邢驘o環(huán)圖（不存在回路的AOV網(wǎng)）的頂點(diǎn)以特定的先后次序排序醉蚁，所謂特定的先后次序排序是使得所有有向邊<u,v>的兩個頂點(diǎn)在序列中都遵頊u在v前面罪针。
（注：之所以是無環(huán)悬蔽，是因?yàn)樵仄h(huán)存在的話棒仍，有些頂點(diǎn)無法分先后）
舉個例子
這個圖的拓?fù)渑判蚴潜ィ珹BCD或ACBD，拓?fù)渑判虻慕Y(jié)果可能是多種的降狠。
但如果AOV圖有環(huán)对竣，拓?fù)湫蛄惺遣淮嬖诘摹Ｋ园衽洌負(fù)渑判蚩梢杂脕砼袛郃OV圖是否存在環(huán)否纬。
兩種拓?fù)渑判蛩惴?/h2>
1. Kahn算法
本質(zhì)是減治法，步驟是
- 找到所有入度為0的的頂點(diǎn)
- 這些頂點(diǎn)入棧
- 出棧蛋褥，輸出临燃，并刪除該頂點(diǎn)的出邊，回到第 1 步
按這個次序輸出的就是拓?fù)湫蛄辛恕?/p>
for (i = 0; i < GL->numVertexes; i++)//遍歷所有頂點(diǎn)
if (GL->adjList[i].in == 0)//如果入度為0步脓，入棧
stack[++top] = i;
while (top != 0)
{
getTop = stack[top--]; //取出棧頂元素
printf("%d",GL->adjList[getTop].data);
for (e = GL->adjList[getTop].firstedge; e; e=e->next;)
{ //對剛剛?cè)コ捻旤c(diǎn)的鄰頂點(diǎn)進(jìn)行處理卷谈，遍歷所有鄰結(jié)點(diǎn)
k = e->adjVex;
if( !(--GL->adjList[k].in))//頂點(diǎn)入度減 1 笔链，如果此時入度為0陌凳，入棧
stack[++top] = k;
}
}
2. 基于dfs的拓?fù)渑判?/h3>
與dfs算法本身有一定的區(qū)別访忿，是通過dfs算法的順序去遍歷頂點(diǎn)危纫，但是輸出拓?fù)渑判虻臅r候是需要新的順序的系宫。
dfs的順序厢呵，第一個頂點(diǎn)铆铆，第一個頂點(diǎn)的其中一個鄰頂點(diǎn)蝶缀，然后是不斷的訪問下一個鄰頂點(diǎn)，直到?jīng)]有之后薄货，返回第一個頂點(diǎn)翁都，訪問其未訪問過的鄰頂點(diǎn)。
顯然谅猾，這樣是不符合拓?fù)渑判虻捻樞虻谋浚裕覀冊谑褂胐fs進(jìn)行拓?fù)渑判虻臅r候税娜，進(jìn)行了修改坐搔。
此時的順序是，dfs訪問順序巧涧，但是其訪問的第一個結(jié)點(diǎn)是最深的結(jié)點(diǎn)薯蝎，接著是最深結(jié)點(diǎn)的上一個結(jié)點(diǎn)，一直到第一個結(jié)點(diǎn)谤绳，不訪問第一個結(jié)點(diǎn)占锯，而是進(jìn)而向第一個結(jié)點(diǎn)的未被訪問的鄰結(jié)點(diǎn)開始訪問這一方向的最深結(jié)點(diǎn)。直到第一個結(jié)點(diǎn)的所有鄰結(jié)點(diǎn)都被訪問了缩筛，在訪問第一個結(jié)點(diǎn)消略。
可遞歸調(diào)用dfs
注：
- 每次訪問時，并不輸出瞎抛，而是加入棧中艺演。最后開始把所有元素出棧，才是真正的拓?fù)湫蛄小?/li>
- 方法二：記錄每個頂點(diǎn)訪問的次序桐臊，最后逆序輸出胎撤。
void dfs(int tag)
{
visited[tag] = 1; //標(biāo)記訪問過該頂點(diǎn)
Vex p = GL->adjList[tag].firstedge;
while( !visited[p->vex] && p)
{
//遍歷該頂點(diǎn)的鄰頂點(diǎn)，遞歸停止條件是沒有鄰頂點(diǎn)断凶，或都被訪問過
dfs(p->vex);
p = p->next;
}
stack[++top] = tag;
}
