連結成分

無向グラフの連結成分は、経路を使って互いに到達でき、これ以上頂点を追加できない頂点集合だ。一回の DFS や BFS が見つけるのは始点の成分だけ。全成分を数えるには全頂点を走査し、未訪問の頂点ごとに塗りつぶしを始める。全体で O(V + E) 時間、開始した回数が成分数になる。

外側のループで多くの頂点をスキップするのは、それらが以前の塗りつぶしで既に分類されたからだ。色のない頂点に着いたときだけ、新しい成分が見つかる。0 から一度探索するだけでは、他の成分を見落とす。

外側の走査が必要な理由

外側は for start in range(n) で各頂点を調べる。色があればスキップし、なければ新しい成分を作る。その頂点から到達可能な全頂点を塗ってから、走査を続ける。

本レッスンの塗りつぶしは、明示的なスタックを使う反復 DFS で、プッシュ時に色を付ける。始点を記録してプッシュし、頂点をポップしては未着色の隣接頂点に現在の成分の色を付けてプッシュする。スタックが空になるまで繰り返す。

無向グラフでは到達可能性が対称になる。a から b へ行ければ戻ることもできるため、成分内のどこから始めても全体を塗れる。キューを使って BFS に替えても、成分内の順序が変わるだけで分割は変わらない。成分を決めるのはグラフだ。

静的な無向グラフのネットワーク群、格子の島、関連項目の分類に向く。辺が順次追加される場合は Union-Find で同じ分割を更新できる。有向グラフで相互到達可能な集合が必要なら強連結成分を求める。二回走査する Kosaraju 法や、一回の DFS を使う Tarjan 法などが必要で、ここでの塗りつぶしをそのまま使うことはできない。

連結成分を求めるステップ

既定の八頂点は三つの群に分かれる。三角形 {0, 1, 2} の辺は 0–1、1–2、2–0、組 {3, 4} の辺は 3–4、鎖 {5, 6, 7} の辺は 5–6、6–7。外側は 0 から 7 へ走査する。

1. 未着色の 0 で成分 #1 を開く。0 を記録してプッシュし、ポップしたら 1 と 2 を塗ってプッシュする。2、1 の順にポップするが、隣接頂点は全て #1 に属する。スタックが空になり、{0, 1, 2} が完成する。
2. 1 は #1 に属するのでスキップする。
3. 2 も #1 なのでスキップする。外側の走査が来る前に塗りつぶしが分類している。
4. 未着色の 3 で #2 を開く。3 をプッシュしてポップし、4 を塗ってプッシュする。4 の隣接頂点 3 は記録済み。スタックが空になり、{3, 4} が完成する。
5. 4 は #2 なのでスキップする。
6. 未着色の 5 で #3 を開く。5 から 6、7 へ塗る。7 の隣接頂点 6 は記録済みなので、スタックが空になり {5, 6, 7} が完成する。
7. 6 は #3 なのでスキップする。
8. 7 も #3 なのでスキップし、走査を終える。

結果は 3 成分。外側は 8 回反復し、塗りつぶしを 3 回始め、5 回スキップする。外側が各頂点に来るとき、その頂点は新成分の始点か、着色済みのスキップ対象のどちらかに必ず当たり、両方にはならない。

一つにつながったグラフのプリセットでは、一回塗りつぶした後は全てスキップする。分散プリセットには孤立頂点があり、辺がなくてもその頂点で塗りつぶしが始まる。全頂点が孤立するプリセットでは辺が一本もなく、n 回の塗りつぶしとゼロ回のスキップになる。

時間計算量と空間計算量

外側は V 頂点を一度ずつ調べる。全ての塗りつぶしを合わせても、各頂点は一度ずつプッシュとポップを行い、各無向辺は両端から一度ずつ検査される。成分ごとにグラフ全体のコストを払うわけではなく、合計が O(V + E) となる。

色の記録とスタックは O(V) 空間。例えば星形グラフの中心を展開すると、他の頂点がまとめてスタックに入り、O(V) 個を保持しうる。この反復実装では長い鎖が大きなスタックを必要とするとは限らず、再帰スタックと区別する必要がある。

境界ケース

• 一頂点は一成分。塗りつぶしは隣接頂点がないので終了する。
• 孤立頂点は辺がなくても大きさ一の成分。外側の走査で調べる必要がある。
• 全頂点が連結なら、一回塗りつぶして残りをスキップする。
• 全頂点が孤立していれば最大の n 成分。全頂点で塗りつぶしを始める。

よくある間違い

1. DFS/BFS を一回だけ実行する。始点の成分しか見つからないので、外側から探索を再開する。
2. 辺のない頂点を忘れる。成分数も分割も誤る。
3. ポップ時に印を付ける。最初のポップ前に同じ頂点を何度もプッシュでき、スタックが膨らむ。実装によっては数え方も壊れる。本実装ではプッシュ時に記録する。
4. 連結成分と強連結成分を混同する。有向辺では到達可能性が対称でないため、Kosaraju 法や Tarjan 法などの SCC アルゴリズムが必要になる。
5. DFS と BFS で成分が変わると思う。探索順は変わっても、無向グラフの連結成分は変わらない。