Hello アルゴで学ぶグラフの走査：幅優先探索（BFS）と深さ優先探索（DFS）の原理・実装・計算量

2026-09-07 13:54:08作者：宣聪麟

「Hello アルゴ」（hello-algo）は、アニメーションとコードを併用してデータ構造とアルゴリズムを学べるオープンソースのチュートリアルで、本書の日本語版ドキュメントは ja/docs/ に配置されています。本記事はその中核トピックのひとつである「グラフの走査（graph traversal）」に焦点を当て、木の走査を特殊ケースとして内包するグラフの幅優先走査（BFS） と深さ優先走査（DFS） を、アルゴリズムの考え方、実装コード、計算量分析の3点から体系的に解説します。読み終えると、Python・C++・Cなど多言語で用意された graph_bfs / graph_dfs の実装を読み解き、訪問済み頂点の管理や走査順序の非一意性といったポイントを押さえた上で、自分の問題に合わせて走査アルゴリズムを選定・実装できるようになります。

グラフの走査とは：木の走査の一般化

木は「一対多」の関係を表しますが、グラフは任意の「多対多」の関係を表現でき、より高い自由度を持ちます。したがって木はグラフの特殊なケースとみなせ、木の走査操作もグラフの走査操作の特殊なケースです。木の走査が「根から全てのノードを漏れなく訪れる」操作であるように、グラフの走査は「始点となる頂点から全ての頂点を漏れなく訪れる」操作です。

グラフと木はいずれも走査を実現するために探索アルゴリズムを用います。グラフの代表的な走査方法は以下の2種類に分けられます（対応コードは graph_bfs.c と graph_dfs.c などで確認できます）。

幅優先走査（BFS: Breadth-First Search）：近い頂点から遠い頂点へ、層ごとに外側へ広がっていく走査。
深さ優先走査（DFS: Depth-First Search）：行けるところまで進み、行き止まりになったら戻る走査。

本記事で繰り返し登場する前提知識として、グラフの表現方法である隣接リスト（graph_adjacency_list.py、graph_adjacency_list.c）と、グラフの基本操作（頂点・辺の追加削除）は graph_operations.md で解説されています。以降の走査コードは「指定した頂点の隣接頂点をすべて取得できる」この隣接リスト表現を前提としています。

幅優先走査（BFS）

「近いところから遠いところへ」の走査戦略

幅優先走査は、ある頂点から出発し、常に最も近い頂点を優先して訪問し、層ごとに外側へ広がっていく走査方法です。 下図のように左上の頂点から出発すると、まずその頂点のすべての隣接頂点（第1層）を走査し、続いて次の頂点のすべての隣接頂点（第2層）を走査します。これを繰り返し、すべての頂点を訪問し終えた時点で終了します。

アルゴリズムの実装：キューと訪問済みハッシュ集合

BFS は通常キューを用いて実装します。キューは「先入れ先出し（FIFO）」の性質を持ち、これは BFS の「近いところから遠いところへ」という考え方と本質的に一致します。基本的な手順は次の3ステップです。

走査の開始頂点 startVet をキューに追加し、ループを開始します。
ループの各反復で、キュー先頭の頂点を取り出して（デキュー）訪問を記録し、その後その頂点のすべての隣接頂点をキューの末尾に追加します。
手順 2. を繰り返し、すべての頂点が訪問されると終了します。

頂点の重複走査を防ぐため、どの頂点が訪問済みかを記録するハッシュ集合 visited を用います。

ヒント：ハッシュ集合とは ハッシュ集合は value を持たず key だけを格納するハッシュテーブルとみなせます。 $O (1)$ の時間計算量で key の追加・削除・検索・更新ができ、key の一意性に基づいてデータの重複排除などの場面で広く使われます。BFS / DFS では「訪問済み頂点の重複排除」に最適なデータ構造です。

本リポジトリの日本語版コードから、Python 実装の核心部分を見てみましょう（全文は graph_bfs.py）。

def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """幅優先探索"""
    # 頂点の走査順序
    res = []
    # 訪問済み頂点を記録するためのハッシュ集合
    visited = setVertex
    # BFS の実装にキューを用いる
    que = dequeVertex
    # 頂点 vet を起点に、すべての頂点を訪問し終えるまで繰り返す
    while len(que) > 0:
        vet = que.popleft()  # 先頭の頂点をデキュー
        res.append(vet)      # 訪問した頂点を記録
        # この頂点のすべての隣接頂点を走査
        for adj_vet in graph.adj_list[vet]:
            if adj_vet in visited:
                continue     # 訪問済みの頂点をスキップ
            que.append(adj_vet)  # 未訪問の頂点のみをキューに追加
            visited.add(adj_vet) # この頂点を訪問済みにする
    # 頂点の走査順を返す
    return res

実装上の重要なポイントは、頂点をキューに追加する時点で visited へ登録することです。仮に「デキューした時点」で訪問済みにする実装にすると、同じ頂点が複数回キューに積まれ、重複訪問が発生します。C++ 版（graph_bfs.cpp）では unordered_set<Vertex *> と queue<Vertex *> を用いて同じロジックを実現しています。

また C 版の graph_bfs.c は、キューと訪問済み配列を自前実装しています。isVisited 関数は配列を線形走査するため $O (n)$ となり、Python/C++ 版のハッシュ集合 $O (1)$ とは実装上の差がありますが、これは「C 言語に標準のハッシュ集合がない」という制約に合わせた教育的な代替実装です。言語機能の違いがアルゴリズムの本質（FIFO キュー + 訪問済み管理）を変えないことを対比して学べる好例といえます。

BFS のアルゴリズムの流れを、頂点ごとの状態遷移として下図シリーズで追うことができます（graph_traversal.assets に step1 〜 step11 が格納されています）。

<1>〜<3>：始点をキューへ投入し、第1層の隣接頂点を順にキューへ追加。
<4>〜<7>：第2層、第3層へとキューから取り出して訪問を記録。
<8>〜<11>：すべての頂点を訪問し、キューが空になって終了。

走査順序列は一意ではない

!!! question "幅優先走査の順序列は一意ですか？" 一意ではありません。幅優先走査は「近いところから遠いところへ」の順で走査することだけを要求し、同じ距離（同一層）にある複数の頂点の走査順は任意に入れ替えて構いません。上図を例にすると、頂点 $1$ と $3$ の訪問順は交換でき、頂点 $2$ 、 $4$ 、 $6$ の訪問順も任意に入れ替えられます。

つまり BFS は「層の順序だけ」を保証し、同一層内の順序はグラフの隣接リスト内の並びや実装に依存します。

計算量の分析

時間計算量：すべての頂点は1回ずつキューに入り、1回ずつキューから出るため $O (∣ V ∣)$ です。隣接頂点を走査する過程では、無向グラフの場合すべての辺が2回訪問されるため $O (2 ∣ E ∣)$ となり、全体で $O (∣ V ∣ + ∣ E ∣)$ です。
空間計算量：結果リスト res、ハッシュ集合 visited、キュー que に含まれる頂点数はいずれも最大で $∣ V ∣$ であるため、 $O (∣ V ∣)$ です。

深さ優先走査（DFS）

「行き止まりまで進んで戻る」の走査戦略

深さ優先走査は、まず行けるところまで進み、進めなくなったら戻る走査方法です。 下図のように、左上の頂点から出発し、現在の頂点の隣接頂点のひとつを訪問して、行き止まりに達するまで進んだら一つ前の頂点へ戻り、再び別の方向へ進んで行き止まりまで進んで戻る、という操作を繰り返し、すべての頂点の走査が完了するまで続けます。

アルゴリズムの実装：再帰と訪問済みハッシュ集合

この「行き止まりまで進んでから戻る」パターンは、通常再帰に基づいて実装されます。BFS と同様に、頂点の重複訪問を避けるために訪問済みハッシュ集合 visited を用います。Python 実装の核心部分は次のとおりです（全文は graph_dfs.py）。

def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex):
    """深さ優先走査の補助関数"""
    res.append(vet)  # 訪問した頂点を記録
    visited.add(vet) # この頂点を訪問済みにする
    # この頂点のすべての隣接頂点を走査
    for adjVet in graph.adj_list[vet]:
        if adjVet in visited:
            continue  # 訪問済みの頂点をスキップ
        # 隣接頂点を再帰的に訪問
        dfs(graph, visited, res, adjVet)


def graph_dfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """深さ優先探索"""
    # 頂点の走査順序
    res = []
    # 訪問済み頂点を記録するためのハッシュ集合
    visited = set[Vertex]()
    dfs(graph, visited, res, start_vet)
    return res

補助関数 dfs が「現在の頂点の訪問記録 → 各隣接頂点への再帰」を行い、visited を引数で受け渡して共有する点がポイントです。再帰呼び出しのスタックがそのまま「探索経路の深さ」を担うため、明示的なスタックを用意する必要がありません。C++ 版（graph_dfs.cpp）も同一の構造で、unordered_set<Vertex *> &visited を参照渡ししています。C 版（graph_dfs.c）では、訪問済み配列 res そのものを探索済み判定に使う実装になっています。

過程の追跡：再帰の「下降」と「バックトラック」

深さ優先走査のアルゴリズムの流れは、下図の step1 〜 step11（graph_traversal.assets）で確認できます。

直線の破線は下向きの再帰呼び出しを表し、新しい頂点を訪問するために新たな再帰メソッドが開始されたことを意味します。
曲線の破線は上向きのバックトラックを表し、この再帰メソッドがすでに戻って、呼び出し元の位置までたどり着いたことを意味します。

理解を深めるには、図とコードを結びつけて、各再帰メソッドがいつ開始し、いつ戻るかを頭の中で（あるいは紙に書き出して）シミュレーションしてみるのが効果的です。

走査順序列は一意ではない

!!! question "深さ優先走査の順序列は一意ですか？" 幅優先走査と同様に、深さ優先走査の順序列も一意ではありません。ある頂点が与えられたとき、どの方向を先に探索してもよく、つまり隣接頂点の順序は任意に入れ替えられ、それでも深さ優先走査になります。

この「順序の自由度」は木の走査と対応づけて考えるとわかりやすいです。木の走査を例にすると、「根 → 左 → 右」「左 → 根 → 右」「左 → 右 → 根」はそれぞれ先行順（pre-order）、中間順（in-order）、後行順（post-order）走査に対応します。これらは3種類の異なる走査優先順位を表していますが、いずれも「1本の経路を深く掘り下げてから戻る」という意味では深さ優先走査に属します。すなわち、DFS の順序列は「隣接頂点をどの順で試すか」の選択次第で変わりうるのです。

計算量の分析

時間計算量：すべての頂点は1回ずつ訪問されるため $O (∣ V ∣)$ 、すべての辺は2回ずつ訪問されるため $O (2 ∣ E ∣)$ 、よって全体で $O (∣ V ∣ + ∣ E ∣)$ です。
空間計算量：結果リスト res とハッシュ集合 visited に含まれる頂点数は最大で $∣ V ∣$ であり、再帰の深さも最大で $∣ V ∣$ （グラフが極端な直線状の場合）であるため、 $O (∣ V ∣)$ です。なお、再帰実装の空間消費はコールスタック上に積まれるため、頂点数が非常に大きいグラフでは反復 + 明示的スタックへの置き換えを検討する場合もあります。

BFS と DFS の比較と使い分け

BFS と DFS はどちらもすべての頂点を $O (∣ V ∣ + ∣ E ∣)$ で走査しますが、訪問順の性質が異なります。

観点	幅優先走査（BFS）	深さ優先走査（DFS）
基本戦略	近い頂点から遠い頂点へ、層ごとに拡張	1本の経路を深く掘り下げ、行き止まりで戻る
主要データ構造	キュー（FIFO）	再帰（コールスタック）
訪問順序の性質	始点からの「距離（層）」が単調非減少	経路の深さを優先
代表的な用途	最短経路（無重み）、層ごとの到達性調査	連結成分の検出、トポロジカルソート、迷路探索など
空間計算量	$O(	V
時間計算量	$O(	V

※ 代表用途はアルゴリズムの一般論としての整理であり、本リポジトリの当該章の範囲を超える内容です。

動作確認：リポジトリのコードを実行してみる

本リポジトリでは各章のコードを言語ごとに実行できます。日本語版のグラフ走査コードは以下にあります。

各コード末尾の Driver Code では、次のような無向グラフを構築して走査結果を出力します。

BFS 用グラフ：頂点 $0$ 〜 $9$ （頂点数 $∣ V ∣ = 10$ 、辺数 $∣ E ∣ = 12$ ）。辺は $0$ - $1$ , $0$ - $3$ , $1$ - $2$ , $1$ - $4$ , $2$ - $5$ , $3$ - $4$ , $3$ - $6$ , $4$ - $5$ , $4$ - $7$ , $5$ - $8$ , $6$ - $7$ , $7$ - $8$ 。
DFS 用グラフ：頂点 $0$ 〜 $6$ （ $∣ V ∣ = 7$ ）。辺は $0$ - $1$ , $0$ - $3$ , $1$ - $2$ , $2$ - $5$ , $4$ - $5$ , $5$ - $6$ 。

たとえば Python の BFS コードは、頂点 $0$ を始点として 0 -> 1 -> 3 -> 2 -> 4 -> 6 -> 5 -> 7 -> 8（同一層内の順序は実装依存で変わりうる）のような走査列を vets_to_vals(res) で数値に変換して表示します。実行環境の構築方法や Docker による一括実行については installation.md を参照してください。

まとめ

グラフの走査は木の走査の一般化であり、BFS（キューによる層次拡張） と DFS（再帰による深掘りとバックトラック） の2系統があります。
どちらも訪問済み頂点を記録するハッシュ集合が必須であり、これがないと巡回グラフで無限ループに陥ります。
BFS も DFS も時間計算量は $O (∣ V ∣ + ∣ E ∣)$ 、空間計算量は $O (∣ V ∣)$ ですが、訪問順の性質が異なるため用途に応じて使い分けます。
両者の走査順序列はどちらも一意ではありません。木の先行順・中間順・後行順は DFS の3つの特殊ケースとみなせます。