使用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中实现它。我们将编写两个函数:拓扑排序和topologicalSortHelper来帮助递归地标记和探索图。
示例
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()); } }
你可以使用以下方法进行测试:
Learn JavaScript in-depth with real-world projects through our JavaScript certification course. Enroll and become a certified expert to boost your career.
示例
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
广告