資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究使用 JavaScript DFS 進行拓撲排序
有向圖的拓撲排序或拓撲排序是其頂點的線性排序，對於從頂點 u 到頂點 v 的有向邊 UV，在排序中 u 位於 v 之前。這僅在有向圖中才有意義。
拓撲排序很有用的地方很多。例如，假設你正在按照食譜製作菜餚，其中有一些步驟是轉到下一步的必經步驟。但其中一些步驟可以並行執行。類似地，在大學選課時，一些高階課程有一些先修課程，這些先修課程本身可能是更高階課程的先修課程。例如 −
示例
/** * CS101 CS102 * / \ / * CS204 CS340 * \ /| \ * CS380 | CS410 * \ | / * CS540 */
在上圖中，考慮是否要學習一個級別的課程，首先必須學習與它相連的所有上述級別的課程。以下是上圖的一些可能的拓撲排序 −
CS101 -> CS204 -> CS102 -> CS340 -> CS410 -> CS380 -> CS540 CS102 -> CS101 -> CS340 -> CS204 -> CS410 -> CS380 -> CS540
讓我們用 JavaScript 來實現這一點。我們會編寫 2 個函式，即拓撲排序和拓撲排序助手，以幫助遞迴地標記和探索圖表。
示例
topologicalSortHelper(node, explored, s) {
explored.add(node);
// Marks this node as visited and goes on to the nodes
// that are dependent on this node, the edge is node ----> n
this.edges[node].forEach(n => {
if (!explored.has(n)) {
this.topologicalSortHelper(n, explored, s);
}
});
// All dependencies are resolved for this node, we can now add
// This to the stack.
s.push(node);
}
topologicalSort() {
// Create a Stack to keep track of all elements in sorted order
let s = new Stack(this.nodes.length);
let explored = new Set();
// For every unvisited node in our graph, call the helper.
this.nodes.forEach(node => {
if (!explored.has(node)) {
this.topologicalSortHelper(node, explored, s);
}
});
while (!s.isEmpty()) {
console.log(s.pop());
}
}您可以使用以下程式碼進行測試 −
示例
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addDirectedEdge("A", "C");
g.addDirectedEdge("A", "B");
g.addDirectedEdge("A", "D");
g.addDirectedEdge("C", "D");
g.addDirectedEdge("D", "E");
g.addDirectedEdge("E", "F");
g.addDirectedEdge("B", "G");
g.topologicalSort();我們建立的圖表如下 −
示例
/** * A * / | \ * C | B * \ | | * D G * | * E * | * F */
輸出
這會顯示以下輸出 −
A B G C D E F
更新於： 2020 年 6 月 15 日
1,000 多次瀏覽
廣告