拓撲排序計算機

使用 Kahn 演算法或 DFS 計算有向無環圖 (DAG) 的拓撲排序。支援檢測環路、報告環路路徑、建立並行執行分層視圖、支援字典序最小排序，並在互動式圖表上動畫演示每個步驟。

拓撲排序計算機

⚡ 試試範例：

線性鏈穿衣順序課程先修晨間常規構建目標鄰接表範例包含環路流水線 DAG

輸入格式

→ 邊列表 (A→B)

⧇ 鄰接表 (A: B, C)

圖形數據

邊格式：A -> B（也接受 →, =>, :）。最多 80 個頂點 / 800 條邊。

鄰接格式：A: B, C, D — 每行一個頂點，後跟其直接後續頂點。

演算法

Kahn 演算法（字典序）提供唯一且可復現的順序。DFS 後序遍歷是經典的深度優先方法。

Embed 拓撲排序計算機 Widget

拓撲排序計算機

拓撲排序計算機可計算有向無環圖 (DAG) 頂點的線性排序，使得從 u 到 v 的每條有向邊都讓 u 排在 v 之前。您可以邊列表或鄰接表的形式輸入圖形，本工具將使用 Kahn 演算法或 DFS 後序遍歷返回拓撲順序、偵測環路（並給出確切路徑）、將任務分組為並行執行層、計算有效排序的總數，並在交互式圖表上以動畫演示每個步驟。

什麼是拓撲排序？

給定一個有向圖 G = (V, E)，拓撲排序（或稱拓撲順序）是其頂點 v₁, v₂, …, vₙ 的線性排列，使得對於每一條有向邊 (u → v)，u 在排列中都出現在 v 之前。當且僅當圖中沒有有向環（即該圖為 DAG）時，才存在拓撲排序。排序結果通常不是唯一的：當多個頂點同時入度為零時，一個圖可以有多個有效的拓撲排序。

拓撲順序定義

V 的一個置換 (v₁, v₂, …, v_n) 是拓撲排序，若且唯若
對於 E 中的每條邊 (u → v)：position(u) < position(v)

此計算機使用的演算法

Kahn 演算法 (基於 BFS，1962)

Kahn 演算法是最直觀的拓撲排序方法。在每一步中，它挑選一個入度為零（沒有指向它的邊）的頂點，將其追加到輸出中，並通過減少其每個後續頂點的入度來將其從圖中「移除」。當有多個入度為零的頂點時，可以使用最小堆（得到字典序最小排序）或 FIFO 隊列（得到插入順序）來打破僵局。Kahn 演算法的運行時間為 O(|V| + |E|)，且兼具環路偵測功能：如果隊列清空後仍有頂點入度 > 0，則圖中存在環路。

Kahn 演算法 (偽代碼)

Kahn(G):
  Q ← { v ∈ V : indeg(v) = 0 }
  L ← [ ]
  當 Q 不為空：
    u ← Q.pop()
    L.append(u)
    對於每條邊 u → v：
      indeg(v) -= 1
      如果 indeg(v) = 0：Q.push(v)
  如果 |L| < |V|：報告環路
  否則：返回 L

DFS 後序遍歷 (Tarjan, 1976)

DFS 演算法執行深度優先搜索，每當一個頂點完成探索（即其所有後續頂點都已被完全探索）時，將其壓入棧中。最後反轉棧即可得到有效的拓撲排序。環路偵測非常自然：遇到一個仍在處理中（標記為 GRAY）的頂點意味著找到了回邊，因此該圖不是 DAG。DFS 後序遍歷的運行時間同樣為 O(|V| + |E|)。

DFS 後序遍歷 (偽代碼)

DFS-Topo(G):
  對於 V 中的每個頂點 u：color[u] ← WHITE
  L ← 空棧
  對於 V 中的每個頂點 u：
    如果 color[u] = WHITE：visit(u)
  返回 reverse(L)

visit(u):
  color[u] ← GRAY
  對於每條邊 u → v：
    如果 color[v] = GRAY：報告環路
    如果 color[v] = WHITE：visit(v)
  color[u] ← BLACK; L.push(u)

並行執行層級

DAG 的分層視圖將其頂點劃分為不同的級別，使得每條邊都從編號較低的層級指向編號較高的層級。同一層中的頂點相互獨立，因此可以並行執行。層級數量等於最長路徑長度加一 — 這就是 DAG 的關鍵路徑，即在擁有無限並行能力的情況下，完成所有任務所需的最少順序輪次。只要輸入是 DAG，此計算機就會自動生成分層視圖。

環路偵測

如果圖中包含有向環，則無法進行拓撲排序。我們的計算機將報告確切的環路路徑（例如 A → B → C → A）並在視覺化圖表中以紅色突出顯示環路邊。移除環路上的任何一條邊都足以恢復無環性。

輸入格式

邊列表

將每條有向邊寫為 源點 -> 目標點，以逗號或換行符分隔。接受的箭頭變體：->, →, =>, -->, :。您也可以連寫邊：A -> B -> C 是 A->B 和 B->C 的簡寫。頂點標籤可以是字母、數字、下劃線、連字符和點。

A -> B, B -> C, A -> C
C -> D
Shirt -> Tie -> Jacket

鄰接表

寫下每個頂點、一個冒號及其直接後續頂點（它指向的頂點）。沒有後續頂點的頂點仍需要佔一行，例如 D:。

A: B, C
B: D
C: D
D:

如何使用此計算機

選擇格式： 通過單選按鈕在邊列表和鄰接表之間切換。
輸入圖形： 粘貼您的數據或點擊快速範例（穿衣順序、課程先修、構建目標、包含環路的圖形等）。
選擇演算法： Kahn 字典序以獲得唯一且可復現的順序；插入順序以保留輸入順序；DFS 後序遍歷用於經典深度優先方法；或選擇顯示全部以並排查看所有排序。
點擊「進行拓撲排序」： 排序結果、環路偵測、分層視圖、關鍵路徑長度、有效排序總數以及交互式圖表將顯示在下方。
探索： 按下播放鍵觀看每個頂點逐步輸出的過程。入度標記會實時更新。拖拽任何節點可調整佈局。

實際應用

構建系統與編譯器

make、Bazel、Gradle 和 npm 等工具會對其構建目標進行拓撲排序，以便每個目標僅在其所有相依項編譯完成後才進行編譯。相依圖中的環路通常被報告為致命錯誤 — 構建系統無法決定從哪裡開始。

任務調度

項目經理使用 DAG 來捕捉任務相依關係。拓撲排序提供了有效的執行順序，而分層視圖則提供了無限並行下的最少輪次。最長鏈是決定項目工期的關鍵路徑。

課程先修規劃

大學課程目錄是一個 DAG：邊代表先修關係。拓撲順序是一個有效的學習計劃，而分層結構則告訴學生在每個學期中哪些課程組可以並行修讀。

電子表格重新計算

當一個單元格發生變化時，電子表格必須按相依順序重新計算每個下游單元格 — 這就是對單元格相依 DAG 進行拓撲排序。循環引用（環路）會被應用程式拒絕。

軟體包管理器與插件加載器

Apt、pip、Homebrew、Maven 和無數插件框架通過對其相依 DAG 進行拓撲排序來解決安裝或加載順序。

符號解析與指令調度

編譯器使用拓撲排序來排列聲明，而 CPU 使用數據相依 DAG 在重排序緩衝區中調度指令，以避免違反數據冒險。

計算拓撲排序的數量

對於一個具有 n 個頂點的 DAG，截然不同的有效拓撲排序數量範圍可以從 1（全序鏈）到 n!（無邊圖）。計算確切數量在一般情況下是 #P-complete 問題，但對於最多 16 個頂點的圖形，此計算機使用位掩碼動態規劃公式進行枚舉：f(S) = Σ f(S ∪ {v})，其中 v ∉ S 且其前驅頂點皆在 S 中。

複雜度與性能

時間： Kahn 演算法和 DFS 後序遍歷的運行時間均為 O(|V| + |E|) — 與圖的大小成線性關係。
空間： O(|V|) 用於入度跟踪和輸出順序，外加 O(|V| + |E|) 用於鄰接結構。
環路偵測： 內置於兩種演算法中。Kahn 在 |輸出| < |V| 時偵測到環路；DFS 在發現回邊（GRAY 鄰居）時偵測到環路。
此工具限制： 交互式視覺化支持最多 80 個頂點和 800 條邊。計數功能限制在 16 個頂點以內。

常見問題

什麼是拓撲排序？

有向無環圖的拓撲排序是其頂點的線性排序，使得從 u 到 v 的每條有向邊都讓 u 排在 v 之前。它代表了在尊重相依關係的情況下處理任務的有效順序。

此計算機使用哪種演算法？

計算機同時運行 Kahn 演算法和 DFS 後序遍歷。Kahn 演算法重複移除入度為零的頂點並減少其後續頂點的入度。DFS 後序遍歷執行深度優先搜索並反轉完成順序。兩者的運行時間均為 O(|V| + |E|)。

如果我的圖形有環怎麼辦？

具有有向環的圖沒有拓撲排序。計算機將偵測到環路，在視覺化圖表中以紅色突出顯示，並報告確切的環路路徑，以便您查看應移除哪些邊使圖形變為 DAG。

什麼是字典序最小的拓撲順序？

當存在多個有效的拓撲排序時，在每一步始終挑選字母順序最小且入度為零的頂點，即可獲得字典序最小的排序。此計算機預設的 Kahn 模式會返回此唯一排序，該排序穩定且易於復現。

什麼是分層或級別視圖？

分層視圖根據距任何源點的最長路徑長度對頂點進行分組。同一層中的頂點之間沒有相依關係，因此可以並行執行。層數等於最長相依鏈加一，代表了完成所有任務所需的最少並行輪次。

一個圖形可以有多個有效的拓撲排序嗎？

是的。如果在 Kahn 演算法的任何步驟中有多個入度為零的頂點，則接著可以挑選其中任何一個。此計算機可計算最多 16 個頂點的圖形中截然不同拓撲排序的確切數量。

Kahn 演算法和 DFS 後序遍歷有什麼區別？

Kahn 演算法是自頂向下的：它重複挑選源點（入度 0）並首先輸出它們。DFS 後序遍歷是自底向上的：它先完成匯點並將其前置於順序中。兩者均為 O(|V| + |E|) 並產生有效的拓撲排序，但通常結果不同。Kahn 演算法更容易並行化以及適配字典序；DFS 則更容易與其他基於 DFS 的分析（如強連通分量）相結合。

此工具支持的最大圖形大小是多少？

計算機支持最多 80 個頂點和 800 條邊。計算有效拓撲排序總數的功能限制在 16 個頂點，因為該問題屬於 #P-complete，狀態空間按 2ⁿ 增長。交互式視覺化和演算法動畫可流暢支持至完整限制大小。

延伸閱讀

引用此內容、頁面或工具為：

"拓撲排序計算機" 於 https://MiniWebtool.com/zh-tw/拓撲排序計算機/，來自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 團隊製作。更新日期：2026年4月20日

您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。

拓撲排序計算機

拓撲排序計算機

什麼是拓撲排序？

此計算機使用的演算法

Kahn 演算法 (基於 BFS，1962)

DFS 後序遍歷 (Tarjan, 1976)

並行執行層級

環路偵測

輸入格式

邊列表

鄰接表

如何使用此計算機

實際應用

構建系統與編譯器

任務調度

課程先修規劃

電子表格重新計算

軟體包管理器與插件加載器

符號解析與指令調度

計算拓撲排序的數量

複雜度與性能

常見問題

什麼是拓撲排序？

此計算機使用哪種演算法？

如果我的圖形有環怎麼辦？

什麼是字典序最小的拓撲順序？

什麼是分層或級別視圖？

一個圖形可以有多個有效的拓撲排序嗎？

Kahn 演算法和 DFS 後序遍歷有什麼區別？

此工具支持的最大圖形大小是多少？

延伸閱讀

進階數學計算:

常用工具: