【超基本】初心者に贈るアルゴリズム論 ～幅優先探索～
スポンサーリンク
幅優先探索とは
幅優先探索はグラフの探索方法の1つです．
始点からの距離の順に頂点を訪問する方法です．
例えば，あなたが部屋でスマホをなくしたとします．
今いる部屋に隣り合っている部屋を全部探してから，それら部屋の奥の部屋をすべて探し，それでも見つからなければさらに奥の部屋...と探していくのが幅優先探索です．
一方で，ある隣の部屋からなるべく奥の部屋まで探して，見つからなければ最初の部屋に戻り，別の隣の部屋からなるべく奥の部屋まで探す方法が深さ優先探索です．
それではコードを見てみましょう．
実装例
# 隣接行列 am = [[0, 1, 0, 1, 1, 0], # s(0) [1, 0, 1, 0, 1, 0], # 1 [0, 1, 0, 0, 1, 0], # 2 [1, 0, 0, 0, 1, 1], # 3 [1, 1, 1, 1, 0, 1], # 4 [0, 0, 0, 1, 1, 0]] # 5 def BFS(am): visit = [0] * len(am) # 訪問済 or 未訪問 queue = [] # s(0)を訪問 visit[0] = 1 queue.append(0) print('Q=' + str(queue) + '\n') while queue: u = queue.pop(0) # キューから頂点uを取り出す adj = am[u] # uの各隣接頂点 for i in range(0, len(adj)): if adj[i] == 1 and visit[i] == 0: # 隣接している & 未訪問 visit[i] = 1 queue.append(i) print('u=' + str(u)) print('adj(u)=' + str([i for i, x in enumerate(adj) if x == 1])) print('Q=' + str(queue) + '\n') BFS(am)
出力
Q=[0] u=0 adj(u)=[1, 3, 4] Q=[1, 3, 4] u=1 adj(u)=[0, 2, 4] Q=[3, 4, 2] u=3 adj(u)=[0, 4, 5] Q=[4, 2, 5] u=4 adj(u)=[0, 1, 2, 3, 5] Q=[2, 5] u=2 adj(u)=[1, 4] Q=[5] u=5 adj(u)=[3, 4] Q=[]
上から順番に見ていきましょう．
下図のような無向グラフがあります．
これを隣接行列であらわすと，
となります．
隣接行列とは，グラフの頂点と頂点の隣接関係を表す正方行列です．
頂点uと頂点vが隣り合っているとき(u,v)成分は1，隣り合っていないときは0になります．
例えば，頂点1と頂点2は隣り合っているので(1,2)成分は1，頂点1と頂点3は隣り合っていないので(1,3)成分は0です．
これをプログラム上で表現するには，二次元配列を使って，
am = [[0, 1, 0, 1, 1, 0], # s(0)
[1, 0, 1, 0, 1, 0], # 1
[0, 1, 0, 0, 1, 0], # 2
[1, 0, 0, 0, 1, 1], # 3
[1, 1, 1, 1, 0, 1], # 4
[0, 0, 0, 1, 1, 0]] # 5と書きます．
visit = [0] * len(am) # 訪問済 or 未訪問 queue = []
visitは頂点に訪問したかどうかを保存する配列です．
頂点の数だけ0で初期化します．
queueはキューです．
始点からの距離の順に頂点を訪問するためには，先に訪問した方から調べていく必要があるので，先入れ先出しのキューを使用します．
visit[0] = 1 queue.append(0)
まず，始点sに訪問するので，visit[0]に1を入れます．
そして，queueに0を入れます．
while queue: u = queue.pop(0) # キューから頂点uを取り出す adj = am[u] # uの各隣接頂点 for i in range(0, len(adj)): if adj[i] == 1 and visit[i] == 0: # 隣接している & 未訪問 visit[i] = 1 queue.append(i)
queueが空になるまでwhileループを回します．
queueが空になるとすべての頂点を調べたということなので終了します．
ループに入ると，まずはqueueの先頭から要素を取り出します．
popの引数である0は，sのことではなくキューの先頭のことなので注意してください．
その後，頂点uの隣接頂点をひとつずつ見ていき，uに隣接していて未訪問の頂点があれば，visitを1にしてキューに入れます．
実行すると以下のように動きます．
（ページ下部の参考文献を参考に作成）
sを訪問，Q={s}
u=s，adj(u)={1,3,4}，1,3,4を訪問，Q={1,3,4}
u=1，adj(u)={s,2,4}，2を訪問，Q={3,4,2}
u=3，adj(u)={s,4,5}，5を訪問，Q={4,2,5}
u=4，adj(u)={s,1,2,3,5}，訪問なし，Q={2,5}
u=2，adj(u)={1,4}，訪問なし，Q={5}
u=5，adj(u)={3,4}，訪問なし，Q={}
参考
