JavaScriptで実装する深さ優先探索（DFS）の仕組みとサンプルコード

深さ優先探索（DFS：Depth-First Search）は、兄弟ノード（同一階層の頂点）よりも先に子ノードを訪問するグラフ探索アルゴリズムです。つまり、探索範囲の「幅」を広げる前に、まず特定のパスの「深さ」を最後までたどるのが特徴です。DFSを実装する際には、スタック（再帰を利用する場合はプログラムのコールスタック）が一般的に使われます。

DFSの動作手順

• 隣接する未訪問の頂点を訪問し、訪問済みとしてマークします。表示したうえで、スタックにプッシュします。
• 隣接する未訪問の頂点が見つからない場合は、スタックから頂点をポップします（隣接する未訪問頂点を持たない頂点がすべてポップされていきます）。
• スタックが空になるまで、ルール1とルール2を繰り返します。

それでは、DFSトラバーサルが実際にどのように進むのかを、段階的な図解で確認してみましょう。

ステップ	探索の様子	説明
1		スタックを初期化します。
2		頂点Sを訪問済みとしてマークし、スタックにプッシュします。Sの未訪問の隣接ノードを調べると、候補は3つあります。本例ではアルファベット順に選択することにします。
3		頂点Aを訪問済みとしてマークし、スタックにプッシュします。SとDがAに隣接していますが、対象になるのは未訪問ノードのみです。
4		Dを訪問して訪問済みとしてマークし、スタックにプッシュします。Dに隣接するBとCはどちらも未訪問なので、ここでもアルファベット順に選択します。
5		Bを選択し、訪問済みとしてマークしてスタックにプッシュします。しかしBには未訪問の隣接ノードがないため、Bをスタックからポップします。
6		スタックの先頭を確認して直前のノードへ戻り、そのノードに未訪問ノードが残っていないかを調べます。ここではDがスタックの先頭にあります。
7		Dの未訪問の隣接ノードはCのみとなりました。そこでCを訪問し、訪問済みとしてマークしてスタックにプッシュします。

Cにも未訪問の隣接ノードはないため、未訪問の隣接ノードを持つノードが見つかるまでスタックからポップを続けます。このケースでは該当するノードが存在しないため、スタックが空になるまでポップされます。

JavaScriptでの実装例

DFS(node) {
    // スタックを作成し、初期ノードを追加する
    let s = new Stack(this.nodes.length);
    let explored = new Set();
    s.push(node);

    // 最初のノードを探索済みとしてマーク
    explored.add(node);

    // スタックが空になるまで処理を続ける
    while (!s.isEmpty()) {
        let t = s.pop();

    // スタックから取り出された要素をログに出力
        console.log(t);

    // 1. edgesオブジェクトから、このノードに直接接続されたノードを検索
    // 2. すでに探索済みのノードをフィルタリング
    // 3. 未探索の各ノードを探索済みとしてマークし、スタックにプッシュ
        this.edges[t]
        .filter(n => !explored.has(n))
        .forEach(n => {
            explored.add(n);
            s.push(n);
        });
    }
}

実装は非常にシンプルです。ポイントは、幅優先探索（BFS）で使っていたキューをスタックに置き換えるだけという点です。これこそが両者の決定的な違いです。なお、DFSは再帰によっても実装できますが、大きなグラフではコールスタックの追跡のために余分なメモリを消費するため、このケースでは再帰は避けるのが賢明でしょう。

動作確認

次のコードで実際に試すことができます。

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.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");

g.DFS("A");

実行結果

上記のコードを実行すると、次の出力が得られます。

A
D
E
F
B
G
C