使用Javascript DFS进行拓扑排序

Z时代
2024-01-10
分类：综合

有向图的拓扑排序或拓扑排序是其顶点的线性排序，这样对于从顶点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);
   //将该节点标记为已访问，然后继续到节点
   // 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);
      }
   });
   //该节点的所有依赖关系都已解决，我们现在可以添加
   //这到堆栈。
   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();

我们创建的图看起来像-