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

なお、正しいトポロジカル順序は1つとは限らず、複数存在する場合があります。どちらの順序でも、各科目がその前提科目より後に配置されているという条件を満たしています。

JavaScriptでの実装

それでは、これをJavaScriptで実装してみましょう。グラフ全体を走査する topologicalSort メソッドと、ノードを再帰的に訪問・マークするための topologicalSortHelper メソッドの2つの関数を作成します。

DFS（深さ優先探索）ベースのアルゴリズムでは、まずノードを訪問済みとしてマークし、そのノードに依存するノードを再帰的に探索します。すべての依存関係が解決された時点で、そのノードをスタックに積みます。最後にスタックから取り出すことで、正しいトポロジカル順序が得られます。

topologicalSortHelper(node, explored, s) {
    explored.add(node);
    // このノードを訪問済みとしてマークし、
    // このノードに依存するノード（辺 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());
    }
}

このアルゴリズムの計算量は、各ノードと各辺をそれぞれ1回ずつ処理するため、O(V + E) となります（V は頂点数、E は辺数）。これは非常に効率的です。

コードのテスト

以下のコードで動作を確認できます。

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

A から始まり、その依存先である B、G が先に処理され、その後 C、D、E、F と続いています。すべての有向辺について、始点の頂点が終点の頂点より前に配置されており、正しいトポロジカル順序が得られていることが分かります。