9.5 演習¶

9.5.1 確認問題¶

1. 同じグラフを 2 つの方法で表す¶

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

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

解答

隣接リストは次のとおりです。
```
A: B, C
B: A, C
C: A, B, D
D: C
```
隣接行列は次のとおりです。

A B C D

A 0 1 1 0

B 1 0 1 0

C 1 1 0 1

D 0 0 1 0
隣接行列では A 行 D 列を直接見ればよいため、任意の 2 頂点が直接つながっているかを調べるのに適しています。
頂点が多く、辺が少ない場合、隣接リストは実際に存在する辺だけを記録します。そのため、頂点のすべての組に対して領域を用意する隣接行列よりも、一般に空間を節約できます。

2. 幅優先走査と深さ優先走査の訪問順序¶

無向グラフの頂点は A、B、C、D、E、辺は A-B、A-C、B-D、C-D、D-E です。

A から開始し、未訪問の隣接頂点が複数ある場合はアルファベット順に選ぶものとします。

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

解答

BFS の訪問順序は A, B, C, D, E です。まず A から辺 1 本で到達できる B、C を訪問し、次により遠い D、E を訪問します。
DFS の訪問順序は A, B, D, C, E です。現在の頂点から未訪問の隣接頂点へ順に進むため、まず A → B → D → C と進みます。C に新しい隣接頂点がなければ D に戻り、次に E を訪問します。
グラフには、たとえば A-B-D-C-A のような閉路があります。訪問済みの頂点を記録しないと、閉路に沿って同じ頂点を何度も訪問し、走査が正常に終了しない可能性があります。

3. 1 回の BFS でグラフ全体を訪問できるか¶

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

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

解答

A からは A、B、C だけを訪問できます。
すべての頂点を訪問できていません。D、E は別の互いにつながった部分を作り、F は単独の頂点です。これらと A の間には経路がないため、A から到達できません。
3 回の BFS の開始頂点は順に A、D、F で、それぞれ {A, B, C}、{D, E}、{F} を訪問します。したがって、このグラフには 3 つの連結成分があります。

9.5.2 プログラミング演習¶

1. 無向グラフに経路が存在するかを判定する¶

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

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

解法のヒント

各無向辺は、両方の向きで隣接リストへ追加する必要があります
グラフには閉路がある可能性があるため、訪問済みのノードを必ず記録します
source から開始し、destination に出会ったら true を返します。走査を終えても出会わなければ false を返します

LeetCode