拓?fù)渑判蚴窃趺磁判虻?/h1>

發(fā)布時(shí)間：2021-07-02 17:21:27 來源：億速云 閱讀：197 作者：chen 欄目：互聯(lián)網(wǎng)科技

這篇文章主要講解了“拓?fù)渑判蚴窃趺磁判虻摹?，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“拓?fù)渑判蚴窃趺磁判虻摹卑桑?/p>

方法：1、找到圖中的一個(gè)入度為0的結(jié)點(diǎn)，將此節(jié)點(diǎn)從圖中剔除并加入到序列E中；2、將1中找到的結(jié)點(diǎn)的全部關(guān)聯(lián)的邊從圖中去掉；3、重復(fù)1,2直到圖中的全部結(jié)點(diǎn)被去除或無法找到入度為0的結(jié)點(diǎn)為止。

本教程操作環(huán)境：windows7系統(tǒng)、Dell G3電腦。

1. 找到圖中的一個(gè)入度為0的結(jié)點(diǎn)，將此節(jié)點(diǎn)從圖中剔除并加入到序列E中

2. 將1中找到的結(jié)點(diǎn)的全部關(guān)聯(lián)的邊從圖中去掉

3. 重復(fù)1,2直到圖中的全部結(jié)點(diǎn)被去除或無法找到入度為0的結(jié)點(diǎn)為止

若此時(shí)圖中的結(jié)點(diǎn)數(shù)為0則找到了拓?fù)湫蛄?，若此時(shí)圖中結(jié)點(diǎn)數(shù)不為0說明圖中存在環(huán)，無法進(jìn)行拓?fù)渑判颉?/p>

擴(kuò)展資料：

對(duì)一個(gè)有向無環(huán)圖(Directed Acyclic Graph簡(jiǎn)稱DAG)G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對(duì)頂點(diǎn)u和v，若邊<u,v>∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡(jiǎn)稱拓?fù)湫蛄?。?jiǎn)單的說，由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判颉?/p>

執(zhí)行步驟

由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械耐負(fù)渑判蛩惴ㄖ饕茄h(huán)執(zhí)行以下兩步，直到不存在入度為0的頂點(diǎn)為止。

(1) 選擇一個(gè)入度為0的頂點(diǎn)并輸出之；

(2) 從網(wǎng)中刪除此頂點(diǎn)及所有出邊。

循環(huán)結(jié)束后，若輸出的頂點(diǎn)數(shù)小于網(wǎng)中的頂點(diǎn)數(shù)，則輸出“有回路”信息，否則輸出的頂點(diǎn)序列就是一種拓?fù)湫蛄小?/p>

感謝各位的閱讀，以上就是“拓?fù)渑判蚴窃趺磁判虻摹钡膬?nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)拓?fù)渑判蚴窃趺磁判虻倪@一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！