グラフ DFS で連結成分の数を数える
塊がいくつあるかは、目では数えられない
前のレッスンでは起点を 1 つ決めて、そこから届く範囲の大きさを数えました。今度は範囲ではなく 塊の数 を知りたい。つながりの一覧だけを渡されて、「このネットワークはいくつのグループに分かれていますか」と聞かれる状況です。
点が 6 つなら絵を描けば数えられます。10,000 点になると描けません。しかも、どの点が同じ塊に属するのかは、一覧を眺めても分かりません。
数え方は 1 つです。まだ訪れていない点を見つけたら、そこを新しい塊の入口とみなして、そこから届く範囲を全部訪問済みにする。この「新しい入口を見つけた回数」が、そのまま塊の数になります。
行けるところまで行って、戻る
範囲を塗りつぶす役は、深さ優先探索 (DFS) が向いています。1 本の道を行けるところまで進み、行き止まりで 1 歩戻って別の道へ移る。迷路で片手を壁につけて歩くときの動きです。塊の中を余さず塗るのが目的なので、近い順に広げる必要はありません。
この動きは再帰と相性がよく、フォルダの中を潜っていく処理と同じ形になります。
Python
def count_files(folder):
total = 0
for entry in folder:
if isinstance(entry, list):
total += count_files(entry) # 中へ潜る
else:
total += 1
return total潜れるだけ潜って、底に着いたら戻ってくる。DFS もこれと同じで、次の隣へ移る前に、今の隣の先を全部片づけます。
再帰を使わずスタックでも書けます。行き先を積んでおき、最後に積んだもの から取り出すと、同じ動きになります。
Python
org = {
"部長": ["課長A", "課長B"],
"課長A": ["山田", "佐藤"],
"課長B": ["鈴木"],
"山田": [], "佐藤": [], "鈴木": [],
}
stack = ["部長"]
while stack:
person = stack.pop() # 最後に積んだものが出る
print(person)
stack.extend(org[person])出力は 部長、課長B、鈴木、課長A、佐藤、山田 の順です。課長B の下を先に全部見てから課長A へ戻っているのが、深く潜る動きです。前のレッスンのキューを使うと、課長A と課長B を先に並べてから下へ降ります。取り出す側が先頭か末尾か、違いはそれだけです。
上の例は組織図なので輪がなく、訪問済みの確認をしていません。グラフでは輪をたどって戻ってくるので、積む前に訪問済みかどうかを見る 1 行が必要です。
数えるのは外側
count を増やす場所を間違えると、答えがまるで変わります。塗りつぶしの中で増やすと「訪問した点の数」になってしまい、結果は必ず点の総数になります。増やしてよいのは、外側のループで まだ訪問していない点を見つけたとき だけです。
再帰で書く場合、Python の再帰の深さは既定で 1,000 前後です。点が鎖のように長くつながっていると途中で止まるので、sys.setrecursionlimit を上げるか、スタック版に切り替えます。
やってみよう
n=6, edges=[[0,1],[1,2],[3,4]]を紙に描く。5 番はどこにもつながっていないので、それ自体が 1 つの塊- 辺が 1 本もないとき、答えは点の数と同じになる
- 全部が 1 本の鎖でつながっているとき、答えは 1 になる
要件
- DFS (再帰 or スタックを使った反復) で実装すること
- 訪問済み配列を使って未訪問の起点を見つけたときだけカウントすること
- 無向エッジは両方向に隣接リストへ追加すること
入出力例
countComponents(6, [[0,1],[1,2],[3,4]]) → 3
countComponents(4, []) → 4
countComponents(4, [[0,1],[1,2],[2,3]]) → 1
countComponents(5, [[0,1],[1,2],[2,0],[3,4]]) → 2
countComponents(1, []) → 1
countComponents(5, [[0,1],[0,2],[0,3],[0,4]]) → 1ヒント
