????拓?fù)渑判蛑械膱D一定是有方向的。因?yàn)橛蟹较蚰鼙硎緝蓚€(gè)頂點(diǎn)之間的優(yōu)先關(guān)系，誰(shuí)在誰(shuí)的前面。不能形成環(huán)，因?yàn)橐坏┬纬森h(huán)了，幾個(gè)頂點(diǎn)的優(yōu)先關(guān)系就不能排序了。

?????一個(gè)無(wú)環(huán)的有向圖稱為有向無(wú)環(huán)圖（Directed Acycline Graph,DAG）

????有向無(wú)環(huán)圖是描述一個(gè)工程，計(jì)劃，生產(chǎn)，系統(tǒng)等流程的有效工具。一個(gè)大工程可分為若干個(gè)子工程（活動(dòng)），活動(dòng)之間通常有一定的約束，例如先做什么活動(dòng)，什么活動(dòng)完成后才可以開(kāi)始下一個(gè)活動(dòng)。

????用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系的有向圖，稱為頂點(diǎn)表示活動(dòng)的網(wǎng)（Activity On Vertex Nextwork）,簡(jiǎn)稱AOV網(wǎng)。

????在AOV網(wǎng)中，若從頂點(diǎn)i 到頂點(diǎn)j 之間存在一條有向路徑，稱頂?shù)?i 是頂點(diǎn) j 的前驅(qū)，或者稱頂點(diǎn) j 是頂點(diǎn) i 的后繼。若<i,j>是圖中的弧，則稱頂點(diǎn) i 是頂點(diǎn) j 的直接前驅(qū)，頂點(diǎn) j 是頂點(diǎn) i 的直接后驅(qū)。

????AOV網(wǎng)中是不允許有環(huán)的，否則會(huì)出現(xiàn)自己是自己的前驅(qū)，陷入死循環(huán)，怎么判斷AOV網(wǎng)中是否有環(huán)呢？ 一個(gè)檢測(cè)的辦法是對(duì)有向圖的頂點(diǎn)進(jìn)行拓?fù)渑判?。如果AOV網(wǎng)中所有的頂點(diǎn)都在拓?fù)湫蛄兄?，則AOV網(wǎng)中必定無(wú)環(huán)。

????拓?fù)渑判?/strong>是指將AOV網(wǎng)中的頂點(diǎn)排成一個(gè)線性序列，改序列必須滿足：若從頂點(diǎn) i 到頂點(diǎn) j 有一條路徑，則該序列中頂點(diǎn) i 一定在頂點(diǎn) j 之前。

????如何進(jìn)行拓?fù)渑判蚰兀?br>

????拓?fù)渑判虻乃枷耄?/strong>

1）選擇一個(gè)無(wú)前驅(qū)的頂點(diǎn)并輸出；（程序中就是找入度為零的點(diǎn)）

2）從圖中刪除該頂點(diǎn)和該頂點(diǎn)的所發(fā)出邊；

3）重復(fù) 1）和 2），直到不存在無(wú)前驅(qū)的頂點(diǎn)；

4）如果輸出的頂點(diǎn)數(shù)小于 AOV網(wǎng)中的頂點(diǎn)數(shù)，則說(shuō)明網(wǎng)中有環(huán)，否則輸出的序列即為拓?fù)湫蛄小?/p>

拓?fù)渑判虿⒉皇俏ㄒ坏摹?/p>

例如：

在上述的描述過(guò)程中，有刪除頂點(diǎn)和邊的操作，實(shí)際上，在程序?qū)崿F(xiàn)上，完全沒(méi)必要真的刪除頂點(diǎn)和邊?？梢詫](méi)有前驅(qū)的頂點(diǎn)（入度為0）暫存到棧中，輸出時(shí)出棧即表示刪除。邊的刪除只需要將其鄰接點(diǎn)的入度減1即可。例如圖中，刪除C0的所有出發(fā)邊，相當(dāng)于將C3,C2,C1頂點(diǎn)入度減1。如下圖所示。

? ?算法步驟：

1） 求出各頂點(diǎn)的入度，存入數(shù)組indegeree[]中，并將入度為0的頂點(diǎn)入棧S。

2）如果棧不為空，則重復(fù)執(zhí)行以下操作：

• ? ? 棧頂元素 i 出棧，并保存到拓?fù)湫蛄袛?shù)組top[]中；
  

• ????頂點(diǎn) i 的所有鄰接點(diǎn)入度減1，如果減1后入度為0，立即入棧S。

3）如果輸出的頂點(diǎn)數(shù)小于AOV網(wǎng)中的頂點(diǎn)數(shù)，則說(shuō)明網(wǎng)中有環(huán)，否則輸出拓?fù)湫蛄小?/p>

首先第一步：圖的存儲(chǔ)：鄰接矩陣，鄰接表，鏈?zhǔn)角跋蛐?/p>

????

??????

標(biāo)簽：