DFSとBFSの違いや実装例をまとめる

いきなりですが、DFSとBFSって紛らわしくないですか？

LeetCodeなどでは、バイナリーツリーを表現するTreeNode型や、隣接リストとしてハッシュマップにリレーションを格納するグラフなど、様々なデータ構造に対してのDFSやBFSの実装が求められます。
探索対象のデータ構造に左右されずに、これらのアルゴリズムのコア概念を理解した上で、それぞれのケースに合わせた実装方法を習得することが重要です。

また、特にDFSはループや再帰を使う方法があり実装方法によって計算方法に違いが出てきます。

この記事では、実装方法に寄らないそれぞれの探索法のコアの概念の解説と、具体的な実装方法の両方についてまとめていきます。

基礎

DFSとBFSは共にグラフや木構造を探索するためのアルゴリズムです。

DFS（深さ優先探索）は、可能な限り深く探索し、行き止まりに達したらバックトラックして次の分岐を探索します。これにより、探索空間を深く掘り下げ、目的のノードに到達するまで探索を続けることができます。

一方、BFS（幅優先探索）は、探索を開始したノードから近いノードを優先的に探索し、すべての隣接ノードを訪れた後に次のレベルのノードを探索します。これにより、探索空間を広くカバーしていくことができます。

例えば以下のようなバイナリーツリーの例を考えます。

    A
   / \
  B   C
 / \   \
D   E   F

このグラフに対して、DFSとBFSの探索順序は以下のようになります。

DFS: A, B, D, E, C, F
BFS: A, B, C, D, E, F

また、以下のようなグラフの場合も同様です。
なお、探索順序は隣接ノードの順序や実装方法によって異なる場合があります。

A--B
|\
| \
C--D--E--F

DFS: A, B, D, E, F, C
BFS: A, B, D, C, E, F

ユースケース

DFSとBFSの探索方法の違いについて理解したところで、互いをどのように使い分ければいいかを考えてみましょう。

DFSは以下のようなケースで効果的です

• グラフの全てのノードを訪問する必要がある場合
• (一つ上とほぼ同義だが)探索対象のノードがルートから遠い、あるいはどこにあるか分からない場合
• メモリ使用量を抑えたいとき（※BFSでは同一レベルのノードを多くキューに保持する必要があるため）

一方で、BFSは次のような場面で力を発揮します

• ノード間の最短経路を求めたいとき
• 探索対象のノードがルートから近いことが予想される場合
• レベル単位での探索や処理が必要なとき（例：ツリー構造の階層処理）

なお、DFSとBFSの時間計算量は、一般的にノード数Vとエッジ数Eを用いて**O(V+E)**と表現されます。

ただし、DFSを後述する再帰で実装する場合には、空間計算量O(H) [H=木の高さ（ルートノードから一番離れたノードまでの数）] が必要となるめ、あまりにも深い木構造に対して再帰で実装されたDFSを使用すると、メモリが逼迫しスタックオーバーフローや処理速度の低下を招く恐れがあります。非再帰（ループとスタック）で実装した場合のDFSの空間計算量は最悪の場合**O(V)**となることがあります。

一方でBFSの空間計算量は、キューに格納されるノードの最大数であるO(W)（Wは最も広いレベルのノード数）またはO(V)（最悪の場合）となります。

実装方法

それでは、DFSとBFSの実装方法について見ていきましょう。

まずは、DFSとBFSの実装方法をデータ構造とループ/再帰の組み合わせで整理します。

	DFS	BFS
バイナリツリー × ループ	✅ Stack	✅ Queue
グラフ × 再帰	✅ 再帰呼び出し	❌ 通常非推奨
グラフ × ループ	✅ Stack	✅ Queue
バイナリツリー × 再帰	✅ 再帰呼び出し	❌ 通常非推奨

BFSは再帰との相性が悪く、通常はループ（Queue）で実装します。これは、再帰がLIFO（後入れ先出し）のコールスタックを利用するのに対し、BFSはFIFO（先入れ先出し）の性質を持つため、再帰で実装するとBFSの本来の動作（幅優先探索）を再現することが困難になるためです。

ご覧の通り、DFSではStackを使ってループで実装する方法と、再帰を使って実装する方法が一般的です。
これは、DFSがルートから探索を始めて途中で他のノードを見つけても、行き止まりに到達するまで深く探索を続けるため、途中で見つけたノード（探索中の経路の分岐点）は、現在の経路を深く探索し終わった後に戻ってこれるよう、後で訪問できるようにするためにLIFO（後入れ先出し）型のデータ構造（Stack）に格納しておく必要があるからです。

対照的にBFSでは、ルートから探索を始めて見つけたノードから順番に探索するため、FIFO（先入れ先出し）型のデータ構造であるQueueを利用した実装が一般的となります。

この後、具体的なDFSとBFSの実装方法について、バイナリツリーとグラフのデータ構造に分けて見ていきますが、その前にバイナリーツリーとグラフの定義を紹介しておきます。

バイナリーツリーについては、LeetCodeでよく使われるTreeNode型を使います。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { // コンストラクタを追加
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

グラフについては、ハッシュマップを使ってノードとその隣接ノードのリストを表現します。
キーはノードの値、値はそのノードに隣接するノードのリストを表します。

Map<Integer, List<Integer>>

DFS (ループ × バイナリーツリー)

まずは、バイナリーツリーに対するDFSのループによる実装方法を見ていきます。

public void dfsTreeIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        System.out.println(current.val);  // Visit
        current = current.right;
    }
}

この実装では、現在のノードとその左の子ノードをStackに順次格納し、可能な限り左のノードを深く探索していきます。
行き止まりに達した（current == nullになった）タイミングで、Stackから最後に追加したノードを取り出して訪問します。

Stackからノードを取り出して訪問した後、そのノードに右の子ノードがあれば、その右の子ノードを次の探索対象とします。右の子ノードがない場合、または右の子ノードの探索が終わった場合は、Stackから次のノード（以前にStackに積まれた、現在のノードの親または祖先）を取り出して探索を続けます。

ちなみにこの探索方法はDFSの中でもIn-Order Traversalと呼ばれる方法で、バイナリーツリーのノードを左→親→右の順に訪問します。
他にもPre-Order Traversal（親→左→右）やPost-Order Traversal（左→右→親）などの方法もありますが、DFSのコアの概念は変わりません。

DFS (再帰 × バイナリーツリー)

void dfsTreeRecursive(TreeNode node) {
    if (node == null) return;
    dfsTreeRecursive(node.left);
    System.out.println(node.val); // Visit
    dfsTreeRecursive(node.right);
}

こちらはバイナリーツリーでのDFSの再帰的な実装です。ループによる実装と比べてかなりシンプルなことが分かりますね。
先ほどのループによる実装では、In-Order Traversalを行うためにWhileループが2重になってしまいましたが、再帰的な実装ではそのような複雑さがなく、ノードを訪問する順序をより直感的に表現できます。

ただし、前述の通り、再帰的な実装では木の高さに応じてスタックが使用されるため、非常に深い木構造に対してはメモリ使用量が増加し、スタックオーバーフローを引き起こす可能性があるので、場合に応じてループによる実装も検討できるとよさそうです。

DFS (ループ × グラフ)

次はグラフに対するDFSの実装方法を見ていきます。

void dfsGraphIterative(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> stack = new Stack<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited.contains(node)) continue;

        visited.add(node);
        System.out.println(node); // Visit

        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
}

バイナリーツリーと違い、グラフではノードが複数の親を持つことがあったり、サイクル（循環）が存在したりするため訪問済みのノードを追跡する必要があります。
訪問済みのノードをSetに格納し、Stackを使って隣接ノードを訪問していきます。
この作業が漏れると無限ループが発生し得るので注意してください。

また、ツリーを探索するときには、In-Order Traversalのような特定の順序でノードを訪問しましたが、グラフではそのような順序は特に決まっていません。訪問する順序は、隣接ノードのリストの順序に依存しているためです。

DFS (再帰 × グラフ)

void dfsGraphRecursive(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
    if (visited.contains(node)) return;

    visited.add(node);
    System.out.println(node); // Visit

    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        dfsGraphRecursive(graph, neighbor, visited);
    }
}

グラフに対するDFSについても再帰的に実装するとスッキリしますね。
この実装では、訪問済みのノードを示すSet引数を引き回して、再帰的に隣接ノードを訪問していきます。

BFS (ループ × バイナリーツリー)

次はバイナリーツリーに対するBFSをループで実装した場合の例を紹介します。

なお、前述の通りBFSはFIFO的にノードを探索するため、LIFO的な再帰的な実装は通常行われません。
そのため、今回のBFSの実装はループによるもののみを紹介します。

void bfsTree(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val); // Visit
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

この実装では、ルートノードから探索を始め、訪問したノードの子ノードをQueueに追加していきます。
QueueはFIFO（先入れ先出し）型のデータ構造であるため、最初に追加されたノードが最初に訪問されます。つまり、ルートノードから近いノードを優先的に探索することが保証されています。

BFS (ループ × グラフ)

void bfsGraph(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println(node); // Visit

        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

グラフをBFSで探索する場合も、バイナリーツリーと同様にQueueを使って実装します。
また、DFSで実装した時と同様に、訪問済みのノードをSetに格納して、再度訪問しないようにします。

訪問済みのノードを訪れないようにする点や、子ノードの数が3以上ある点がバイナリーツリーとの相違点として挙げられるものの、基本的なBFSのアルゴリズムとしては同じです。

まとめ

今回の記事では、DFSとBFSのコアの概念と実装方法について解説しました。

DFSは深く探索し、行き止まりに達したらバックトラックして次の分岐を探索するアルゴリズムであり、BFSはルートから近いノードを優先的に探索するアルゴリズムです。

ループで実装するのか、再帰で実装するのか、または探索対象がツリーなのかグラフなのかによって、実装方法が微妙に異なるため自分みたいに混乱している人が少なくないと思います。

読者の方のDFSとBFSの理解を深める手助けになれば幸いです。