溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

C#中怎么實(shí)現(xiàn)拓?fù)渑判?/h1>
發(fā)布時(shí)間：2021-06-24 17:22:49 來源：億速云 閱讀：369 作者：Leah 欄目：大數(shù)據(jù)

這篇文章給大家介紹 C#中怎么實(shí)現(xiàn)拓?fù)渑判?，?nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

.原理

先來一個(gè)基本定義：

在圖論中，拓?fù)渑判颍═opological Sorting）是一個(gè)有向無環(huán)圖（DAG, Directed Acyclic Graph）的所有頂點(diǎn)的線性序列。且該序列必須滿足下面兩個(gè)條件：

  1. 每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次。

  2. 若存在一條從頂點(diǎn) A 到頂點(diǎn) B 的路徑，那么在序列中頂點(diǎn) A 出現(xiàn)在頂點(diǎn) B 的前面。

有向無環(huán)圖（DAG）才有拓?fù)渑判?，非DAG圖沒有拓?fù)渑判蛞徽f。

例如，有一個(gè)集合它的依賴關(guān)系如下圖：

C#中怎么實(shí)現(xiàn)拓?fù)渑判?></p><p>可以看到他有一個(gè)依賴關(guān)系:</p><ol class=

  • Module D 依賴于 Module E 與 Module B 。

  • Module E 依賴于 Module B 與 Module C 。

  • Module B 依賴于 Module A 與 Module C 。

  • Module C 依賴于 Module A 。

  • Module A 無依賴 。

    • 這個(gè)就是一個(gè) DAG 圖，我們要得到它的拓?fù)渑判?，一個(gè)簡單的步驟如下：

    1. 從 DAG 圖中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并輸出。

    2. 從 DAG 圖中刪除該頂點(diǎn)，以及以它為起點(diǎn)的有向邊。

    3. 重復(fù)步驟 1、2 直到當(dāng)前的 DAG 圖為空，或者當(dāng)前圖不存在無前驅(qū)的頂點(diǎn)為止。

    按照以上步驟，我們來進(jìn)行一個(gè)排序試試。

    C#中怎么實(shí)現(xiàn)拓?fù)渑判?></p><p>最后的排序結(jié)果就是：</p><p>Module D -> Module E -> Module B -> Module C -> Module A</p><p>emmmm，其實(shí)一個(gè)有向無環(huán)圖可以有一個(gè)或者多個(gè)拓?fù)湫蛄械?，因?yàn)橛械臅r(shí)候會(huì)存在一種情況，即以下這種情況：</p><p><img src=

  • 首先初始化隊(duì)列，將 5 與 4 這兩個(gè)入度為 0 的頂點(diǎn)加入隊(duì)列當(dāng)中。

  • 執(zhí)行 While 循環(huán)，條件是隊(duì)列不為空。

  • 之后首先拿出 4 。

  • 然后針對(duì)其指向的頂點(diǎn) 0 與 頂點(diǎn) 1 的入度減去 1。

  • 減去指向頂點(diǎn)入度的時(shí)候同時(shí)判斷，被減去入度的頂點(diǎn)其值是否為 0 。

  • 這里 1 入度被減去 1 ，為 0 ，添加到隊(duì)列。

  • 0 頂點(diǎn)入度減去 1 ，為 1。

  • 隊(duì)列現(xiàn)在有 5 與 1 這兩個(gè)頂點(diǎn)，循環(huán)判斷隊(duì)列不為空。

  • 5 指向的頂點(diǎn) 0 入度 減去 1，頂點(diǎn) 0 入度為 0 ，插入隊(duì)列。

    • 這樣反復(fù)循環(huán)，最終隊(duì)列全部清空，退出循環(huán)，得到拓?fù)渑判虻慕Y(jié)果4, 5, 2, 0, 3, 1 。

    4.深度優(yōu)先搜索實(shí)現(xiàn)

    在參考資料 1 的代碼當(dāng)中使用的是深度優(yōu)先算法，它適用于有向無環(huán)圖。

    有以下有向環(huán)圖 G2：

    C#中怎么實(shí)現(xiàn)拓?fù)渑判?></p><p>對(duì)上圖 G2 進(jìn)行深度優(yōu)先遍歷，首先從入度為 0 的頂點(diǎn) A 開始遍歷：</p><p><img src=

  • 訪問 A 。

  • 訪問 B 。

  • 訪問 C 。

    • 在訪問了 B 后應(yīng)該是訪問 B 的另外一個(gè)頂點(diǎn)，這里可以是隨機(jī)的也可以是有序的，具體取決于你存儲(chǔ)的序列順序，這里先訪問 C 。

    1. 訪問 E 。

    2. 訪問 D 。

    這里訪問 D 是因?yàn)?B 已經(jīng)被訪問過了，所以訪問頂點(diǎn) D 。

    1. 訪問 F 。

    因?yàn)轫旤c(diǎn) C 已經(jīng)被訪問過，所以應(yīng)該回溯訪問頂點(diǎn) B 的另一個(gè)有向邊指向的頂點(diǎn) F 。

    1. 訪問 G 。

    因此最后的訪問順序就是 A -> B -> C -> E -> D -> F -> G ，注意順序還是不太對(duì)哦。

    看起來跟之前的方法差不多，實(shí)現(xiàn)當(dāng)中，其 Sort() 方法內(nèi)部包含一個(gè) visited 字典，用于標(biāo)記已經(jīng)訪問過的頂點(diǎn)，sorted 則是已經(jīng)排序完成的集合列表。

    在字典里 Key 是頂點(diǎn)的值，其 value 值用來標(biāo)識(shí)是否已經(jīng)訪問完所有路徑，為 true 則表示正在處理該頂點(diǎn)，為 false 則表示已經(jīng)處理完成。

    現(xiàn)在我們來寫實(shí)現(xiàn)吧：

    C#中怎么實(shí)現(xiàn)拓?fù)渑判?></p><p><img src=關(guān)于 C#中怎么實(shí)現(xiàn)拓?fù)渑判蚓头窒淼竭@里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

    向AI問一下細(xì)節(jié)

    免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
    AI
    助
    手