グラフ BFS で連結成分サイズを求める
同じ人を 2 回数えてしまう
社内チャットの「誰と誰がつながっているか」の一覧をもらったとします。ある人を起点に、友達の友達までたどって、その輪に何人いるかを数えたい。
紙の上でやってみると、すぐ困ります。A から B へ、B から C へ、C から A へ戻る。ぐるっと一周して A に着いたので、また B へ進んでしまう。輪があると、たどるだけでは永久に終わりません。仮に終わっても、同じ人を何度も数えてしまいます。
木にはこの問題がありませんでした。親から子への一方通行だったからです。グラフは戻ってこられるので、一度訪れた場所を覚えておく 必要があります。
訪問済みの入れ物 (集合や真偽値の配列) を 1 つ用意して、そこに入っていない相手にだけ進む。これがグラフをたどるときの唯一の約束事です。この章の残りのレッスンでも、ずっとこの約束を使います。
つながりの持ち方
もらった一覧は [[0,1],[1,2],[2,0]] のような「辺の並び」です。この形のままだと「0 の隣は誰か」を調べるたびに全部の辺を見ることになります。
そこで探索の前に「0 の隣は [1,2]」という形へ組み替えるのが定番です (隣接リスト)。
点が少なく辺が密なときだけ、n かける n の表に 0 と 1 を書く隣接行列も使われます。
近いところから、輪を広げる
幅優先探索 (BFS) は、起点のすぐ隣を全部見てから、その次の隣を見る、という順で広がります。池に石を落としたときの波紋と同じで、近いところから外へ広がっていきます。
順番の管理には キュー を使います。先に入れたものが先に出るので、先に入った (つまり近い) 相手から順に処理されます。
Python
from collections import deque
rooms = {
"受付": ["会議室", "倉庫"],
"会議室": ["受付", "廊下"],
"倉庫": ["受付"],
"廊下": ["会議室"],
}
def visit_order(start):
seen = {start}
queue = deque([start])
order = []
while queue:
room = queue.popleft()
order.append(room)
for nxt in rooms[room]:
if nxt not in seen:
seen.add(nxt)
queue.append(nxt)
return ordervisit_order("受付") は ['受付', '会議室', '倉庫', '廊下'] を返します。受付の隣を 2 つとも先に処理し、そのあとで 1 つ外側の廊下へ進んでいるのが分かります。
deque を使うのは、先頭を取り出す popleft() が速いからです。ふつうの配列で pop(0) と書くと、取り出すたびに全要素がずれるので遅くなります。JavaScript も同じ理由で shift() を避け、取り出し位置の番号を 1 つずつ進める書き方をします。
一覧が [a, b] の形で来ているとき、a の隣に b を足すだけでは足りません。向きのないつながりなので、b の隣にも a を足します。片方だけだと b 側から出発したときに a へ戻れず、1 つの輪が 2 つに割れて見えます。
訪問済みの印は、キューに入れる瞬間 に付けます。取り出すときに付けると、同じ相手が何度もキューに積まれ、処理する回数が膨らみます。
やってみよう
n=5, edges=[[0,1],[1,2],[2,0],[3,4]]の絵を紙に描く。輪が 2 つに分かれているのが見えるはず- 起点を 0 にしたときと 3 にしたときで、たどり着ける人数が変わることを確かめる
- 辺が 1 本もないとき、起点自身の 1 人だけが数えられることを確かめる
要件
- BFS (幅優先探索) を使って探索すること
- 訪問済み集合を用いて同じノードを 2 度処理しないこと
- 無向エッジは両方向 (a->b, b->a) を扱えるようにすること
入出力例
bfsComponentSize(5, [[0,1],[1,2],[2,0],[3,4]], 0) → 3
bfsComponentSize(5, [[0,1],[1,2],[2,0],[3,4]], 3) → 2
bfsComponentSize(3, [], 0) → 1
bfsComponentSize(4, [[0,1],[1,2],[2,3]], 0) → 4
bfsComponentSize(5, [[0,1],[0,2],[0,3],[0,4]], 2) → 5
bfsComponentSize(6, [[0,1],[1,2],[3,4],[4,5]], 4) → 3ヒント
