JavascriptDFSを使用したトポロジカルソート

有向グラフのトポロジカルソートまたはトポロジカル順序付けは、頂点の線形順序付けであり、頂点uから頂点vまでのすべての有向エッジUVについて、順序付けでuがvの前に来るようにします。これは、有向グラフでのみ意味があります。

トポロジカルソートが非常に理にかなっている場所はたくさんあります。たとえば、レシピに従っているとしましょう。これには、次のステップに進むために必要ないくつかのステップがあります。ただし、これらの一部は並行して実行できます。同様に、大学でコースを選択する際には、より高度なコースの前提条件がいくつかあり、それ自体がさらなるコースの前提条件となる場合があります。例-

例

 /**
   *       CS101  CS102
   *       /       \ /
   *      CS204    CS340
   *       \      /| \
   *       CS380   | CS410
   *          \    | /
   *           CS540
*/

上のグラフで、1つのレベルでコースを受講するかどうかを検討します。最初に、接続されているすべてのコースをその上のレベルから受講する必要があります。以下は、上記のグラフで考えられるトポロジの種類です-

CS101 -> CS204 -> CS102 -> CS340 -> CS410 -> CS380 -> CS540
CS102 -> CS101 -> CS340 -> CS204 -> CS410 -> CS380 -> CS540

これをJavaScriptで実装しましょう。グラフを再帰的にマークして探索するのに役立つ、トポロジカルソートとtopologicalSortHelperの2つの関数を記述します。

例

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