グラフ DFS で連結成分の数を数える

塊がいくつあるかは、目では数えられない

前のレッスンでは起点を 1 つ決めて、そこから届く範囲の大きさを数えました。今度は範囲ではなく 塊の数 を知りたい。つながりの一覧だけを渡されて、「このネットワークはいくつのグループに分かれていますか」と聞かれる状況です。

点が 6 つなら絵を描けば数えられます。10,000 点になると描けません。しかも、どの点が同じ塊に属するのかは、一覧を眺めても分かりません。

数え方は 1 つです。まだ訪れていない点を見つけたら、そこを新しい塊の入口とみなして、そこから届く範囲を全部訪問済みにする。この「新しい入口を見つけた回数」が、そのまま塊の数になります。

行けるところまで行って、戻る

範囲を塗りつぶす役は、深さ優先探索 (DFS) が向いています。1 本の道を行けるところまで進み、行き止まりで 1 歩戻って別の道へ移る。迷路で片手を壁につけて歩くときの動きです。塊の中を余さず塗るのが目的なので、近い順に広げる必要はありません。

この動きは再帰と相性がよく、フォルダの中を潜っていく処理と同じ形になります。

def count_files(folder):
    total = 0
    for entry in folder:
        if isinstance(entry, list):
            total += count_files(entry)   # 中へ潜る
        else:
            total += 1
    return total

潜れるだけ潜って、底に着いたら戻ってくる。DFS もこれと同じで、次の隣へ移る前に、今の隣の先を全部片づけます。

再帰を使わずスタックでも書けます。行き先を積んでおき、最後に積んだもの から取り出すと、同じ動きになります。

org = {
    "部長": ["課長A", "課長B"],
    "課長A": ["山田", "佐藤"],
    "課長B": ["鈴木"],
    "山田": [], "佐藤": [], "鈴木": [],
}

stack = ["部長"]
while stack:
    person = stack.pop()      # 最後に積んだものが出る
    print(person)
    for child in org[person]:
        stack.append(child)

出力は 部長、課長B、鈴木、課長A、佐藤、山田 の順です。課長B の下を先に全部見てから課長A へ戻っているのが、深く潜る動きです。前のレッスンのキューを使うと、課長A と課長B を先に並べてから下へ降ります。取り出す側が先頭か末尾か、違いはそれだけです。

上の例は組織図なので輪がなく、訪問済みの確認をしていません。グラフでは輪をたどって戻ってくるので、積む前に訪問済みかどうかを見る 1 行が必要です。

数えるのは外側

count を増やす場所を間違えると、答えがまるで変わります。塗りつぶしの中で増やすと「訪問した点の数」になってしまい、結果は必ず点の総数になります。増やしてよいのは、外側のループで まだ訪問していない点を見つけたとき だけです。

Python の再帰の深さには上限があります。点が鎖のように長くつながっていると途中で止まるので、演習ではスタック版を使います。

やってみよう

• n=6, edges=[[0,1],[1,2],[3,4]] を紙に描く。5 番はどこにもつながっていないので、それ自体が 1 つの塊
• 辺が 1 本もないとき、答えは点の数と同じになる
• 全部が 1 本の鎖でつながっているとき、答えは 1 になる

演習の隣接リストは、空のリストを for のたびに新しく作って append([]) で加えています。各頂点の隣の入れ物は独立しているので、一つに辺を追加しても他の頂点には増えません。

本文の isinstance(entry, list) は entry がリストかを調べる関数です。

print(isinstance([1, 2], list))  # True
print(isinstance("memo.txt", list))  # False

フォルダをリスト、ファイルを文字列で表す例なので、リストの場合だけ再帰で潜ります。

1. DFS (再帰 or スタックを使った反復) で実装すること
2. 訪問済み配列を使って未訪問の起点を見つけたときだけカウントすること
3. 無向エッジは両方向に隣接リストへ追加すること