グラフの演習問題と解法：隣接リスト・隣接行列・BFS/DFS・連結成分判定を徹底解説（hello-algo）

《Hello 算法》日本語版のグラフ章では、理論解説（グラフ・グラフの基本操作・グラフの走査）に続き、演習ページとして「理解確認問題」と「プログラミング演習」が用意されています。本記事はこの演習ページを主軸に、各問題の解き方・解答・なぜそうなるのかの原理を、リポジトリ内の実装コード（隣接行列・隣接リスト・BFS/DFS）を参照しながら丁寧に解説します。読了後は、「同じグラフを隣接リスト／隣接行列で表し分ける」「訪問順序を手で追跡する」「非連結グラフの連結成分を見極める」「BFS/DFS による経路存在判定を自分で実装する」といった能力が身につきます。

前提知識：この演習を解くための 3 つの柱

演習問題は、本章で学んだ次の 3 つの概念の理解を確認します。

1. グラフの 2 つの表現方法：

   • 隣接行列（adjacency matrix）：$n \times n$ の 0/1 行列で全頂点ペアの辺の有無を表し、判定・辺の追加・削除がすべて $O(1)$、ただし空間は $O(n^2)$。
   • 隣接リスト（adjacency list）：各頂点に隣接頂点のリストを持たせ、実際に存在する辺だけを記録。空間は $O(n + m)$ だが、隣接判定に $O(n)$ かかる場合がある。

   実装例はリポジトリの graph_adjacency_matrix.py と graph_adjacency_list.py にあります。隣接行列は「主対角線に関して対称」「主対角成分は $0$」という特徴を持ち（graph_adjacency_matrix.py の add_edge() は adj_mat[i][j] = 1 と adj_mat[j][i] = 1 を同時に書く）、隣接リストは無向辺を双方向に登録します（graph_adjacency_list.py）。日本語版の解説は グラフの基本操作 の比較表で整理されています。

2. 幅優先走査（BFS）：キューを使い「近い頂点から順に」広がるように訪問。実装は graph_bfs.py で、visited（ハッシュ集合）と deque を併用します。

3. 深さ優先走査（DFS）：再帰（またはスタック）を使い「1 本の道を奥まで進んでから戻る」訪問。実装は graph_dfs.py で、こちらも visited が必須です。

演習を解く前に、グラフ・グラフの走査 を通読しておくと、語彙（隣接・経路・次数・連結）と一致してスムーズに進めます。

確認問題 1：同じグラフを 2 つの方法で表す

無向グラフに 4 つの頂点 A、B、C、D があり、辺は A-B、A-C、B-C、C-D です。

1. このグラフの隣接リストを書いてください。
2. 0 と 1 だけを使って隣接行列を埋めてください。
3. A と D が直接つながっているかを調べるとき、1 つの記録を見るだけで済むのは、どちらの表現方法ですか？
4. 頂点が多く、辺が少ないグラフでは、一般にどちらの表現方法が空間を節約できますか？

問 1-1：隣接リストの書き方

隣接リストは「各頂点がどの頂点と直接つながっているか」を 1 行ごとに列挙します。無向グラフなので、辺 X-Y は X の行にも Y の行にも現れます。

A: B, C
B: A, C
C: A, B, D
D: C

辺が A-B、A-C、B-C、C-D の 4 本あるため、リストには合計 8 個（$2\times 4$）の頂点参照が並ぶ点がポイントです。無向辺の「双方向登録」は、graph_adjacency_list.py の self.adj_list[vet1].append(vet2) と self.adj_list[vet2].append(vet1) に対応します。

問 1-2：隣接行列の書き方

行と列を頂点 A、B、C、D に対応させ、辺があれば 1、なければ 0 を入れます。無向グラフなので行列は主対角線（A-A、B-B、C-C、D-D の 4 マス、すべて 0）に関して対称になります。

	A	B	C	D
A	0	1	1	0
B	1	0	1	0
C	1	1	0	1
D	0	0	1	0

問 1-3：2 頂点の「直接つながり」の判定が得意なのは？

隣接行列では A 行 D 列の 1 マスを参照するだけで判定できます（上表では 0 なので直接接続なし）。これは行列の要素アクセスが $O(1)$ であることの利点そのものです。一方、隣接リストで「A と D がつながっているか」を調べるには A のリストを走査して D を探す必要があり、最悪でリスト長ぶんの比較が要ります。

隣接判定：隣接行列 $O(1)$ ／ 隣接リスト $O(n)$（連結リスト実装の場合）

問 1-4：疎なグラフで空間を節約するのは？

頂点が多く辺が少ない「疎（sparse）なグラフ」では、隣接リストが有利です。隣接リストは実際に存在する辺だけを記録するため空間 $O(n+m)$ で済みます。一方、隣接行列は頂点数 $n$ に対して常に $n\times n$ のマスを確保するため空間 $O(n^2)$ です。$n=4$ のような小さな例では差が目立ちませんが、たとえば頂点が 1 万個で辺が 1 万本程度の現実的なグラフでは、行列は 1 億マスになるのに対し、リストは約 2 万件の記録で済みます。日本語版 グラフ の記述「隣接リストは実際に存在する辺だけを格納し、辺の総数は通常 $n^2$ よりはるかに小さいため、より省スペース」がそのまま解答根拠です。

確認問題 2：幅優先走査と深さ優先走査の訪問順序

無向グラフの頂点は A、B、C、D、E、辺は A-B、A-C、B-D、C-D、D-E です。A から開始し、未訪問の隣接頂点が複数ある場合はアルファベット順に選ぶものとします。

1. 幅優先走査（BFS）の訪問順序を書いてください。
2. 再帰による深さ優先走査（DFS）の訪問順序を書いてください。
3. どちらの走査でも、訪問済みの頂点を記録する必要があるのはなぜですか？

問 2-1：BFS の訪問順序

BFS はキューに「次に訪問する頂点」をため、出発点から辺の本数（距離）が近い順に訪問します。

• 距離 1（A の隣接）：B、C
• 距離 2：B の隣接 D、C の隣接 D（D は重複）→ ここで D
• 距離 3：D の隣接 E

同じ距離の頂点はアルファベット順で選ぶため、答えは A, B, C, D, E です。

キューによる実装では「訪問済みマーク」を入隊時に付けるのが重要なコツです（graph_bfs.py では visited への追加を que.append と同時に行っています）。こうしないと、同一頂点が複数回キューに積まれてしまうからです。

問 2-2：再帰 DFS の訪問順序

DFS は「現在の頂点の未訪問の隣接頂点へ飛び込み、行き止まりになったら巻き戻る」戦略です。

1. A に着き、隣接の B、C をアルファベット順に検討 → B へ。
2. B から未訪問の D へ。
3. D から未訪問の C へ（D の隣接は C、D。D は訪問済みなので C へ）。
4. C に未訪問の隣接はない → D へ戻る。D には他に E が残っている → E へ。

したがって答えは A, B, D, C, E です。

ここで注意したいのは、BFS と DFS の「同じ頂点集合の訪問」でも、訪問順序はまったく異なる点です。BFS は「層ごと」、DFS は「枝を一気に潜る」順になります。日本語版の graph_traversal.md では、両者のアニメーション図とコードが比較されているので、順序の違いを目で追って確認できます。

問 2-3：なぜ visited 記録が必要なのか？

このグラフには A-B-D-C-A という閉路（サイクル） が存在します。訪問済みを記録しないと、閉路をぐるぐる回って同じ頂点を何度も訪れ、走査が終了しない（無限ループする）可能性があります。木（グラフの特殊形）と違い、一般のグラフは閉路を含み得るため、BFS/DFS とも「一度訪れた頂点をスキップする」仕組みが必須です。リポジトリの実装では、この役割をハッシュ集合が担っています（graph_dfs.py の if adjVet in visited: continue、graph_bfs.py も同様）。

確認問題 3：1 回の BFS でグラフ全体を訪問できるか

無向グラフに頂点 A、B、C、D、E、F があり、辺は A-B、B-C、D-E だけです。

1. A から 1 回 BFS を行うと、どの頂点を訪問できますか？
2. 問い 1 の結果から、この 1 回の BFS でグラフのすべての頂点を訪問できたといえますか？その理由も説明してください。
3. すべての頂点をアルファベット順に調べ、未訪問の頂点に出会うたびに新しい BFS を開始します。各 BFS の開始頂点は何ですか？このグラフはいくつの互いにつながっていない部分（連結成分）に分かれますか？

問 3-1：A 起点の BFS

A から到達できるのは辺でつながった範囲だけです。A-B、B-C をたどって A、B、C を訪問できますが、D-E 側も F も A との間に経路がありません。

答え：A、B、C のみ。

問 3-2：全頂点に到達したか

到達していません。D、E は別のつながった部分を作り、F は孤立した単独の頂点です。BFS/DFS は開始頂点と同じ連結成分内しか訪問できません。日本語版の用語では、すべての頂点が連結しているグラフを「連結グラフ」、そうでないものを「非連結グラフ」と呼び（グラフ）、このグラフは後者に当たります。

問 3-3：連結成分の数え方

非連結グラフ全体を走査する定石は「全頂点を順にスキャンし、未訪問の頂点が見つかるたびにそこから新しい走査を開始する」ことです。その理由は、前の走査で訪問済みになった頂点は同じ連結成分に属するため、改めて走査の起点にする必要がないからです。

1. A 未訪問 → BFS 開始、{A, B, C} を訪問。
2. B、C は訪問済み。D 未訪問 → BFS 開始、{D, E} を訪問。
3. E は訪問済み。F 未訪問 → BFS 開始、{F} を訪問。

したがって 3 回の BFS の開始頂点は A、D、F の順で、グラフは 3 つの連結成分（{A, B, C}、{D, E}、{F}）に分かれます。連結成分の個数は、実際の走査では「新しく BFS を開始した回数」としてそのまま計上できます。

プログラミング演習：無向グラフに経路が存在するかを判定する

問題の理解

$n$ 個の頂点を持つ無向グラフが与えられ、頂点には $0$ から $n-1$ までの番号が付いています。配列 edges の各要素 [u, v] は、頂点 u と v の間に無向辺があることを表します。

さらに、始点 source と終点 destination が与えられます。まず edges から隣接リストを作り、次に BFS または DFS を使って、source から destination への経路が存在するかを判定してください。存在する場合は true、存在しない場合は false を返します。グラフには閉路がある場合も、連結していない場合もあります。

これは、前節までの知識をそのまま実装に落とし込む総合問題です。与えられた edges（頂点ペアの配列）を隣接リストへ変換し、source を起点に BFS/DFS を走らせて destination に到達できるかを判定します。

解法のヒント（公式の 3 点）

演習ページでは次のヒントが提示されています。

1. 各無向辺は、両方の向きで隣接リストへ追加する：辺 [u, v] に対して adj[u].append(v) と adj[v].append(u) の両方を実行します。片方だけだと有向グラフとして扱われてしまいます。
2. グラフには閉路がある可能性があるため、訪問済みのノードを必ず記録する：確認問題 2 の問 3 で見たとおり、visited がなければ閉路で無限ループします。
3. source から開始し、destination に出会ったら true を返す：走査を最後まで終えても出会わなければ false を返します。source == destination の場合も true になる点に注意してください。

実装例（BFS バージョン）

ヒントの 3 点を忠実にコード化すると、たとえば次のようになります。隣接リストの「無向辺の双方向登録」「visited による閉路対策」「出会ったら即 true」という構造は、リポジトリの graph_bfs.py にある graph_bfs() の骨格とほぼ一致します。

from collections import deque

def valid_path(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    # 1. edges から隣接リストを構築（無向辺は双方向に登録）
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    # 2. BFS：visited で訪問済みを管理し、キューで幅優先に探索
    visited = [False] * n
    que = deque([source])
    visited[source] = True
    while que:
        vet = que.popleft()
        if vet == destination:      # 3. destination に到達したら true
            return True
        for adj_vet in adj[vet]:
            if not visited[adj_vet]:
                que.append(adj_vet)
                visited[adj_vet] = True
    return False                     # 走査を終えても到達しなければ false

実装例（DFS バージョン）

再帰 DFS で書く場合も、訪問済みマークの管理と「到達したら即 true」の 2 点だけ守れば、graph_dfs.py の dfs() と同じ再帰パターンで解けます。

def valid_path(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * n

    def dfs(vet: int) -> bool:
        if vet == destination:
            return True
        visited[vet] = True
        for adj_vet in adj[vet]:
            if not visited[adj_vet]:
                if dfs(adj_vet):   # どこかの枝で destination に到達
                    return True
        return False

    return dfs(source)

計算量の見積もり

頂点数を $n$、辺の本数を $m$ とすると：

• 隣接リストの構築：各辺を 2 回ずつ追加するため $O(n + m)$ の空間、$O(m)$ の時間。
• BFS / DFS 本体：各頂点・各辺を高々 1 回ずつ訪問するため、どちらも時間 $O(n + m)$、visited 配列の分も含めて空間 $O(n)$（隣接リスト込みなら $O(n + m)$）。

これは「グラフの走査は頂点と辺の総数に比例する」という基本性質をそのまま反映しており、グラフの基本操作 の効率比較の考え方と整合します。

動作確認のポイント

練習で動作を確かめるには、リポジトリの graph_bfs.py や graph_dfs.py の Driver Code を参考に、次のような入力を試すとよいでしょう。

• n = 3, edges = [[0,1],[1,2]], source = 0, destination = 2 → true（一直線につながる）。
• n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 → false（{0,1,2} と {3,4,5} が別の連結成分）。
• n = 1, edges = [], source = 0, destination = 0 → true（同一頂点なので走査開始と同時に一致）。

3 番目の例は「スタート地点がそのままゴール」の境界ケースで、source == destination の扱いを忘れると誤答する典型例です。

まとめ：演習が問う「本質」とは

今回の演習は、どれも「グラフの表現」と「グラフの走査」という 2 つの本質に帰着します。

• 表現の選択：隣接判定や辺の操作を高速化したいなら隣接行列（空間と引き換え）、頂点数が多く辺が少ないグラフなら隣接リスト（時間と引き換え）。問題の制約（$n$、$m$ の規模）を見て選ぶ判断力が問われます。
• 走査の戦略：BFS は距離順・層ごと、DFS は枝優先。いずれも閉路対策の visited が生命線で、非連結グラフでは「開始頂点から届く範囲＝1 つの連結成分」という事実が全体走査の設計を左右します。
• 経路存在判定への応用：「到達可能性」は BFS/DFS どちらでも解ける最も基本的なグラフ問題の一つで、隣接リスト構築 → 走査 → 条件一致で早期 return、という流れは、最短経路や連結成分の数え上げなど、より複雑な問題へつながる土台です。

解説と演習を一通り終えたら、章末の要約ページでグラフの全体像を振り返り、日本語版のコード一式（Python グラフ章 ほか、C++、Java、Go、Rust など多言語の実装がリポジトリに揃っています）を実行して理解を固めることをおすすめします。