有向图的拓扑排序或拓扑排序是其顶点的线性排序,这样对于从顶点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();
我们创建的图看起来像-
/** * A * / | \ * C | B * \ | | * D G * | * E * | * F */
输出结果
这将给出输出-
A B G C D E F