使用 Javascript DFS 进行拓扑排序
front end technologyweb developmentjavascript
有向图的拓扑排序或拓扑排序是其顶点的线性排序，使得对于从顶点 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 来帮助递归标记和探索图形。
示例
topologicalSortHelper(node, explored, s) {
explored.add(node);
// 将此节点标记为已访问并继续访问依赖于此节点的节点
//，边是节点 ----> n
this.edges[node].forEach(n => {
if (!explored.has(n)) {
this.topologicalSortHelper(n, explored, s);
}
});
// 此节点的所有依赖关系都已解析，我们现在可以添加
// 将其添加到堆栈中。
s.push(node);
}
topologicalSort() {
// 创建一个堆栈以按排序顺序跟踪所有元素
let s = new Stack(this.nodes.length);
let explored = new Set();
// 对于图中的每个未访问节点，调用帮助程序。
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();
The graph we created looks like −
示例
/** * A * / | \ * C | B * \ | | * D G * | * E * | * F */
输出
这将给出输出 −
A B G C D E F
