グラフ探索の原理（BFS・DFSと到達可能性）

グラフ探索とは何を解く操作か

グラフ探索は、ある始点から辺をたどって到達できる頂点を漏れなく重複なく列挙する操作です。一見単純ですが、最短経路・連結成分・サイクル検出・トポロジカルソートといった多くの問題が、この一手の上に積み上がっています。

グラフは頂点集合と辺集合で表されます。実装は主に隣接リスト（各頂点ごとに隣接頂点の列を持つ）と隣接行列（V×V のマス目で辺の有無を持つ）の2通りで、疎なグラフでは隣接リストが標準です。探索アルゴリズムが扱うデータの土台はキュー・スタックなので、不安があればデータ構造（配列・リスト・スタック・キュー・マップ）を先に押さえると理解が速まります。

探索の正しさを支えるのは訪問済み管理です。各頂点に「visited」フラグを1つ持ち、一度展開した頂点を二度展開しないことで、サイクルがあっても無限ループに陥らず、各頂点をちょうど1回処理できます。これが全アルゴリズムの共通基盤です。

BFSとDFS：順序を決めるのは取り出し規則だけ

幅優先探索（BFS）と深さ優先探索（DFS）は、骨格はまったく同じで、次に展開する頂点をどの順で取り出すかだけが違います。BFS はキュー（先入れ先出し）、DFS はスタック（後入れ先出し）を使います。

traverse(start):
  visited = 空集合
  frontier = 始点 start を入れた コンテナ      # BFS:キュー / DFS:スタック
  visited に start を追加
  while frontier が空でない:
    u = frontier から1つ取り出す
    for v in u の隣接頂点:
      if v が visited にない:
        visited に v を追加
        frontier に v を入れる

BFS は始点から距離が近い順（辺の本数が少ない順）に層状に広がります。距離 0 の始点、次に距離 1 の頂点群、次に距離 2…という波紋状の展開になり、この性質から重みなしグラフの最短経路（最小の辺数）を副産物として得られます。各頂点を初めてキューに入れた時点の距離が、そのまま始点からの最短距離です。

DFS は1本の道をできるだけ深く進み、行き止まりで引き返して別の枝へ移ります。スタックを使う反復版でも、関数呼び出しスタックを使う再帰版でも本質は同じです。再帰版は記述が簡潔ですが、深いグラフではスタックオーバーフローに注意が要ります。

計算量がともに O(V+E) になる理由

BFS も DFS も、隣接リスト実装での計算量は頂点数 V と辺数 E について O(V+E) です。記法に不安があれば計算量と Big-O 記法を参照してください。

理由は数えれば明らかです。各頂点は visited 管理によりちょうど1回だけ取り出されて展開されます（V 回）。展開のたびにその頂点の隣接辺を走査しますが、すべての頂点の隣接辺の総数は、有向グラフで E、無向グラフで 2E です。したがって辺の走査総数は O(E)。合わせて O(V+E) になります。

頂点の取り出し:   各頂点1回   → O(V)
辺の走査:        各辺を端点側から見る → O(E)（無向は 2E）
合計:                          → O(V + E)

隣接行列で実装すると、各頂点の隣接走査が常に V マスの確認になるため O(V²) に増えます。疎なグラフ（E が V² よりずっと小さい）では隣接リストが有利、密なグラフでは行列も選択肢、という使い分けになります。

メモリは両者とも最悪 O(V) ですが、増え方が違います。BFS は同じ層の頂点を同時にキューへ抱えるため幅が広いグラフで膨らみ、DFS は経路の深さ分のスタックを持つため深いグラフで膨らみます。

到達可能性と連結成分

到達可能性の判定は探索そのものです。始点 s から探索を1回走らせ、終わった時点で頂点 t が visited に入っていれば「s から t へ到達可能」と判定できます。s から到達できる頂点の集合がそのまま探索の結果です。

無向グラフの連結成分は、この到達可能性の自然な拡張です。まだ訪問していない頂点を1つ選んで探索すると、その頂点が属する成分が丸ごと visited になります。次に未訪問の頂点を選んで再び探索…と繰り返し、探索を起動した回数がそのまま連結成分の個数になります。

count_components(G):
  visited = 空集合
  count = 0
  for v in G の全頂点:
    if v が visited にない:
      traverse(v)        # この成分を丸ごと訪問済みにする
      count += 1
  return count

全体としても各頂点・各辺を一度ずつ見るだけなので、計算量は O(V+E) のままです。有向グラフでは「互いに行き来できる」という条件が強くなり、強連結成分という別概念になります（Tarjan や Kosaraju のアルゴリズムが用いられ、これも DFS が土台です）。

行きがけ順・帰りがけ順とその応用

DFS の真価は、頂点をいつ処理するかの2つのタイミングを使い分けられる点にあります。頂点に入った瞬間が行きがけ順（pre-order）、その頂点の全子孫を処理し終えて戻る瞬間が**帰りがけ順（post-order）**です。

dfs(u):
  visited に u を追加
  # ── ここが行きがけ（pre）：u に入った瞬間 ──
  for v in u の隣接頂点:
    if v が visited にない:
      dfs(v)
  # ── ここが帰りがけ（post）：u の子孫を処理し終えた瞬間 ──

サイクル検出は行きがけ/帰りがけの境界を使う代表例です。有向グラフでは各頂点を「未訪問・探索中（スタック上）・完了」の3状態で管理し、**探索中の頂点へ向かう辺（バックエッジ）**を見つけたらサイクルが存在します。単なる訪問済みフラグだけでは「合流（横断辺）」と「後退（サイクル）」を区別できないため、3状態管理が正しさの鍵です。

has_cycle(u):           # 有向グラフ
  state[u] = 探索中
  for v in u の隣接頂点:
    if state[v] == 探索中: return true   # バックエッジ＝サイクル
    if state[v] == 未訪問 and has_cycle(v): return true
  state[u] = 完了
  return false

無向グラフでは、いま来た辺（親）を除いて訪問済みの頂点へ戻る辺があればサイクルです。

帰りがけ順の逆順はトポロジカルソートを与えます。DAG（有向非巡回グラフ）で各頂点を post-order で記録し、その並びを反転すると、すべての辺が前から後ろへ向く順序になります。ビルド依存・タスク順序付けの基礎で、グラフ構造が木に近い場合の議論は平衡木の原理（赤黒木・B木・AVL木）の探索順とも通じます。

まとめ：1つの骨格から広がる世界

BFS と DFS は「未訪問頂点を取り出して展開する」という単一の骨格を共有し、取り出し規則がキューかスタックかだけで挙動が分かれます。どちらも O(V+E) で、訪問済み管理が正しさを支えます。到達可能性・連結成分はこの探索の直接の帰結であり、DFS の行きがけ/帰りがけ順を足場にサイクル検出やトポロジカルソートへ広がります。グラフ問題を前にしたら、まず「これは到達可能性の問題か、順序の問題か」を見極め、適切な探索を骨格として選ぶ——それが原理から組み立てる最短ルートです。