幅優先探索(BFS)を完全に理解した
競プロ典型90問 003:Longest Circular Road を(解説を読んで)実装して幅優先探索を完全に理解したので覚書きをする。
問題概要
N 個の都市と N-1 本の道路があり、道路は都市と都市を双方向に結んでいる。どの都市の間もいくつかの道路を通って移動可能。
任意の都市uと都市vの間に一本だけ道路を新設する。
新設後、同じ道を二度通らずにある都市から同じ都市に戻ってくる経路の長さをスコアとしたとき、考えられる最大スコアはいくつか。
問題の理解
初見だとどう解いていけばいいのか全くわからなかった。BFSを書けたところで、この問題にBFSをどう使うかをわからないとコンテストでは回答できない。
ので、公式解説と照らし合わせて問題を振り返る。
木構造
問題文にある、N 頂点、N-1 辺の連結なグラフは木構造と呼ばれる。
木は、ある頂点が親頂点をひとつだけ持つグラフ。親が複数いるグラフは木ではない。
木の直径
木の特徴として、ある2頂点 u と v の間を双方向に結ぶ辺を 1 本追加したときに、閉路が 1 つ出現する。閉路の長さが u と v の単純パスの長さ +1 になる。
u と v の単純パスが木の中で最も長いとき、『木の直径』と言うらしい。かっこいい。
今回の問題は閉路の長さが問われているので、木の直径+1を求めればよいということ。
木の直径は最短距離問題を2回解くことで求められる、らしい。
- 頂点 1 から各頂点までの最短距離を求める
- 最も最短距離が長かった頂点を u として、頂点 u からの各頂点までの最短距離を求める
- 2で算出した最短距離の中で最大のものが木の直径
最短距離を求める幅優先探索
で、どこで幅優先探索(BFS)を使うかというと、最短距離を求めるところ。木じゃないグラフでもBFSで最短距離が求まるらしい。すごい。
BFSの手順
手を出す前はさぞかし長大なコードを書かないといけないのかなと思っていたけど、アルゴリズムのステップとしてはそんなに多くない。というかこれで最短経路が求まるのがすごい。考えた人すごい。
BFSで使うのは主に3つ。
- キュー Q
- 頂点ごとの最短経路 dist
- グラフ G
Q と dist は1次元配列で実装、G は2次元配列で実装できる。(というかRubyでやるとだいたいそうなる)
以下BFSの手順。(E8さんの本では1オリジンで説明されてたのでここでも1オリジンで書く)
- すべての頂点を白で塗る(白は未探索を表す)
- キュー Q に頂点 1 を追加する。
dist[1]=0として、頂点1を灰色に塗る(灰は探索済を表す) - キュー Q が空になるまで、以下を繰り返す
- Q の 先頭要素 pos を取り出す
- 頂点 pos に隣接した白色の頂点 nex について、
dist[nex]をdist[pos]+1に更新し、Q に nex を追加する。キューへの追加時には頂点を灰色に塗る。
キューが空になった時点の dist に、頂点1から見た全頂点の最短距離が格納されている。
例の本だと1ステップずつ図解されててとてもわかりやすかった。
実装
いつもの通り Ruby で実装した。
def bfs(num, start, graph)
# 始点からの距離
# -1は未探索を表す
dist = Array.new(num) {-1}
# キュー
queue = []
# 始点の情報を追加
dist[start] = 0
queue.push(start)
# キューが空になるまで続ける
while (!queue.empty?)
t = queue.shift
# 取り出したノードに隣接するノード分をすべて調べる
graph[t].each do |it|
next if dist[it] != -1 # 探索済ノードはパスする
# 始点からの距離を格納
# 直前のノードの距離+1
dist[it] = dist[t] + 1
queue.push(it)
end
end
dist
end
配列 dist を -1 で初期化しておくことで探索済かどうかを表すのは競プロっぽくて好き。
Rubyの配列はスタックとして使う場合は push と pop で直感的に使えるのだけど、キューとして使う場合は push shift になるので若干混乱する。
あと、Array#push よりも Array#<< の方が速いらしい。覚えておく。
ちなみに典型90問の方は、このbfsを2回使って木の直径を求めれば解けた。
BFS自体はだいたいわかった(気がする)が、最初の方でも書いたように、問題文を最短経路問題に帰着させられるかどうかが一番の課題なのだと思う。アルゴリズムをただ覚えても勝てないと肝に銘じて研鑽を続けるとする。
あと、計画では1日1問のペースで典型90問をこなすはずだったのだけど、全く予定通りになっていない。まあ焦ってはいけない。今日は寝よう。