9.5 練習問題¶

9.5.1 知識の確認¶

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

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

隣接リストを書いてください。
0 と 1 だけからなる隣接行列を埋めてください。
A と D が直接つながっているかを判定するとき、一つの格納項目を見るだけでよいのはどちらの表現ですか。
頂点が多く、辺が少ないグラフでは、通常どちらが領域を節約できますか。

解答例

隣接リストは次のとおりです。
```
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. 幅優先と深さ優先の訪問順序¶

無向グラフの頂点は 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. 一回の BFS でグラフ全体を訪問できるか¶

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

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

解答例

A から訪問できるのは A、B、C だけです。
全頂点は訪問できていません。D、E は別の連結した部分を作り、F は孤立した頂点です。いずれも A との間に経路がないため、A からは到達できません。
三回の 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