数据结构
网络
关系数据库管理系统(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中实现它。我们将编写两个函数：拓扑排序和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());
}
}你可以使用以下方法进行测试：
示例
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日
浏览量：1K+
广告