グラフのパス存在判定｜コードで実践

グラフのパス存在判定

このレッスンで分かること

O(n + m)

「ノード s からノード t へたどり着けるか？

基本は前 2 レッスンの BFS / DFS と同じですが、1 点だけ大きな違いがあります

グラフのパス存在判定とは

始点と終点が与えられたとき、その間にパスが存在するかを真偽値で返す関数を実装する。本レッスンでは、グラフのパス存在判定の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

「ノード s からノード t へたどり着けるか？」というのは、グラフを扱うときに最初に出てくる問題の 1 つです。SNS の友達関係なら「s さんと t さんは知り合いをたどってつながっているか」、依存関係グラフなら「s の処理は t に影響を与えるか」を判定することになります。

本レッスンでは無向グラフを対象に、ノード数 n、エッジリスト edges、始点 s、終点 t を受け取って、s から t への パスが存在するなら True、なければ False を返す関数 pathExists(n, edges, s, t) を実装します。これまでに学んだ BFS / DFS のどちらでも書けます。

パス存在判定は「t に到達できる頂点集合に t が含まれるか」という形に分解できる。BFS/DFS の応用としてシンプル。

早期終了の重要性

基本は前 2 レッスンの BFS / DFS と同じですが、1 点だけ大きな違いがあります。目的のノードに到達した時点で打ち切る ことです。連結成分のサイズや個数は最後まで走査する必要がありましたが、パス存在判定は「t に着けたら勝ち」なので、見つけ次第 True を返してしまえます。

diagram (will load when visible)

図のポイント (テキスト併記)

上の図では s=0 から t=3 を BFS で探すと 0 -> 1 -> 2 -> 3 の順で到達できます

上の図では s=0 から t=3 を BFS で探すと 0 -> 1 -> 2 -> 3 の順で到達できます。ノード 4、5 は探索されないか、4 は途中まで見られて打ち切られます。

Python での実装 (BFS)

Python

from collections import deque

def pathExists(n, edges, s, t):
    if s == t:
        return True
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = {s}
    queue = deque([s])
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v == t:
                return True
            if v not in visited:
                visited.add(v)
                queue.append(v)
    return False

冒頭で s == t を即 True にしているのは、自分自身は明らかに到達可能だからです (長さ 0 のパス)。ループ中では v == t を見つけた瞬間に True を返して 計算を打ち切る ことで、巨大なグラフでも無駄な探索を防げます。

JavaScript での実装

JavaScript

function pathExists(n, edges, s, t) {
  if (s === t) return true;
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const visited = new Set([s]);
  const queue = [s];
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    for (const v of adj[u]) {
      if (v === t) return true;
      if (!visited.has(v)) {
        visited.add(v);
        queue.push(v);
      }
    }
  }
  return false;
}

基本構造は完全に同じ。Set で訪問管理し、queue に追加するときに visited も同時に立てます。

DFS で書く場合

どちらでも答えは出るが、最短性が必要なら BFS。深く潜って先に答えに辿り着きたいケースでは DFS が有利なこともある。

再帰 DFS でも同じことができます。

Python

def pathExists(n, edges, s, t):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = [False] * n
    def dfs(u):
        if u == t:
            return True
        visited[u] = True
        for v in adj[u]:
            if not visited[v] and dfs(v):
                return True
        return False
    return dfs(s)

「dfs(v) が True を返したら自分も True」というバケツリレー型の書き方が定型です。

計算量

O(n + m)。最悪ケースは t がグラフ上の最遠点にあり、すべて探索する場合です。

よくある間違い

1 つ目は s == t を判定し忘れるパターン。エッジゼロのグラフでも s == t なら True です。2 つ目は s == t を最初に判定し忘れるパターン。visited = {s} を先に立てると始点が訪問済み扱いとなり、t に二度と到達できず誤って False を返す。冒頭で if s == t: return True を入れておくと安全。3 つ目は 見つかった後も探索を続けてしまう こと。return True でループから即抜けないと、計算時間が無駄になります。

やってみよう

s=0, t=3, edges=[[0,1],[1,2],[2,3]] で True が返ること。
s=0, t=4, edges=[[0,1],[1,2],[2,3]] (t が範囲外じゃないけど別成分) で False になることを確認。
自己ループ s == t を試して True になることを確認。

パス存在判定は「最短経路」「サイクル検出」「2 部グラフ」などのもっと複雑なグラフ問題の土台。シンプルだが必須スキル。

よくある質問

Q. この内容は面接でよく聞かれますか？

A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。

Q. 計算量と空間計算量はどっちを優先しますか？

A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。

Q. 問題が解けないときどう取り組めば良いですか？

A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。

次のレッスン

次は BFS で最短経路の長さを求める で、始点と終点が与えられたとき、その間にパスが存在するかを真偽値で返す関数を実装するを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

パス存在判定の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. パス存在判定とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

グラフのパス存在判定