Pythonで誰でも書けるBFS(幅優先探索)
こんばんは、ぱんと申します。
お久しぶりです！私が前回ABC参戦記を書いたのはABC154の時なので、今回は私が灰→茶coderになってから初の競プロ記事ということになります。めでたい(？)
さて、今回は「PythonでBFS(幅優先探索)を簡単に書く方法」についてやっていきたいと思います。
参考にした記事のリンクはその都度記載したので、ぜひ活用してください。
まえがき①記事を書いたきっかけ
この記事を書こうと思ったのは、ABC168Dを解こうとして「Python bfs」で検索した時に以下のことで困ったのがきっかけでした。
・競プロ向きの「入力を受け取る」式のBFSではない記事が多い
・classとか構造体とか使ってる
この2番目が個人的にけっこう嫌で、「classとか分からんし自力でシンプルに実装する方法が知りたいんや！！！！！」ってなったので自分で記事を書きました。
まえがき②注意
・AtCoderの最新バージョンであるPython 3.8.2で動作することを確認しています。以前のバージョンについては未確認です。
・よわよわ茶coderなので表現に正確さが欠けているところがあるかもしれません。分かりやすさを重視したので許してください。
もし間違い等あればコメントでそっと教えてもらえると嬉しいです。
まえがき③この記事の対象者
・今回の記事の対象はPythonでif文、for文の基礎とリスト(二次元配列を含め)が書ける人です。新ABCで例えるとA, B問題ならすんなり解ける人、でしょうか(A, B問題が解けても二次元配列分からない人もそれなりに多いと思うので、この分類は非常に雑です)。二次元配列が怪しいという人は、ググって使い方を理解した上で読んだ方がいいかもしれません。
本編①実装
御託はいいからさっさとコードを見せろ、という人も多いと思うので早速コードです。どん。
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 0
d = deque()
d.append(1)
while d:
v = d.popleft()
for i in graph[v]:
if dist[i] != -1:
continue
dist[i] = dist[v] + 1
d.append(i)
ans = dist[1:]
print(*ans, sep="\n")こちらの記事を参考にしました(リンク先ではC++で実装しています)。
本編②想定入力/実行例/添字のルール
想定している入力
1行目に頂点n個、辺m本
その下の行から辺がどの頂点とどの頂点をつなげているか
が入力される想定です(AtCoderはだいたいこんな感じな気がする)。
例えば頂点4個で辺4本、つながっている頂点が(1, 2)、(2, 3)、(3, 4)、(4, 2)なら
4 4
1 2
2 3
3 4
4 2
と与えられます。
上記実装の実行例
第i行には頂点1からの最短距離が出力されます。なので、ためしに上の入力で実行してみると
0
1
2
2
と出力されます。頂点1から頂点1の距離は0と定義したので1行目は必ず0で、例えば4行目は2なのでこの入力の場合「頂点1から頂点4の最短距離は2」とわかる、ということです。
今回の添字のルール
例えばdist[i]には頂点1から頂点iの最短距離(shortest distance)を入れたいので
dist = [-1] * (n+1)
のようにサイズn+1のリストを作りました。なのでdist[0]に意味はありません(一応0という値を入れてありますが、最後には出力しません)。
同様に、graph[i]には頂点iと直接つながっている頂点番号を入れたいので(後ほど#4で詳しく解説するのでここでは意味がよく分からなくても大丈夫です)、graph[0]にも意味はありません。
リストの添字(インデックス)についてはこちら
本編③実装を1行ずつ解説
競プロやPythonにある程度慣れている方ならこれでいいかもしれませんが、私自身がBFSについて知りたいと思ったときにはここまでの内容では分からなかっただろうなと思うので、より詳しく解説をしていきます。有用な記事へのリンクもさらに充実させました。
先ほどのコードの再掲です。解説に使うため、#1～#8という記号だけ追加でつけています。
from collections import deque #1
n, m = map(int, input().split()) #2
graph = [[] for _ in range(n+1)] #3
for i in range(m): #4
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
dist = [-1] * (n+1) #5
dist[0] = 0
dist[1] = 0
d = deque() #6
d.append(1)
while d: #7
v = d.popleft()
for i in graph[v]:
if dist[i] != -1:
continue
dist[i] = dist[v] + 1
d.append(i)
ans = dist[1:] #8
print(*ans, sep="\n")#1
from collections import deque #1collectionsライブラリのimportです。
「collectionsライブラリからdequeというオブジェクトを取得する」という意味になります。ライブラリとかオブジェクトが何かは私もよく分かっていなくて(おい)、「なんか便利なやつ」くらいの認識です。それでもこの実装はできるので安心してください。
collectionsライブラリやdequeについて詳しく知りたい方はこちら(公式ドキュメント)
dequeについて分かりやすい記事はこちら(初心者にはこちらをおすすめ)
#2
n, m = map(int, input().split()) #21行目の「頂点n個、辺m本」という入力を受け取ります。
Pythonでの競プロの入力受け取りについて親切な記事はこちら
#3
graph = [[] for _ in range(n+1)] #3リスト内包表記を用いて二次元配列graphを作成します。n+1個の[](空リスト)が作られます。リスト内包表記の基本と活用についてはこちら。
のちにこの空リストの中にappendしていきます(ただしgraph[0]は使わないので、最後まで空リストのまま)。
ここで注意したいのが、二次元配列を作るときに
graph = [[]] * (n+1)のようにしないことです(私もこのミスに気付かずずっと悩んでいました)。こうやってしまうと、後でgraph.appendをするときに変な挙動をします(詳しくはこの記事)。
#4
for i in range(m): #4
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)-------------------------------------------
【2020/6/27追記】
グラフ理論の知識不足でわかっていなかったのですが、ここで作るgraphというリストは一般に「隣接リスト」というらしいです。グラフをプログラムで表現するのによく用いられる2つの手法のひとつです(もう一つは「隣接行列」)。
グラフ理論が全く分からない人でも隣接リストがわかるサイトはこちら
-------------------------------------------
入力の2行目以降の、「辺がどの頂点とどの頂点をつなげているか」という部分の受け取りです。私が実装するときにいちばん訳が分からなかったのはこの#4の3, 4行目だったんですが、その部分で実現したいのは「graph[i]には頂点iと直接つながっている(*1)頂点番号を入れる」ということです。
(*1)「頂点iと頂点jが直接つながっている」とは、ここではiとjを結ぶ辺が存在することだとします。
具体的に言うと、2行目以降の入力が
1 3
1 4
2 4
だった場合、頂点1と直接つながっているのは頂点3と4なので、頂点1については
graph[1] = [3, 4]
にしたい、ということです。ここで、graph[1].append(3)とするとgraph[1]に3(頂点3)がappendされる(*2)ので、「頂点1に頂点3が直接つながっている」ことが表現できます。
(*2)
graph[1].append(3)ってなんやねんという人は下のコード例をどうぞ。
graph = [[], [], [], [], []]
graph[1].append(3)
print(graph) #[[], [3], [], [], []]
print(graph[1]) #[3]つまりgraph[1]に関してはgraph[1].append(3)とgraph[1].append(4)をしたいのですが、これは
1 3
1 4
の入力に対してgraph[a].append(b)をすることで実現できます。
同様に頂点3についても、「頂点3に頂点1が直接つながっている」ことを表すためにgraph[3].append(1)をする必要があります。入力"1 3"に対してのgraph[3].append(1)なので、graph[b].append(a)とすれば実現できますね。
これが3, 4行目の
graph[a].append(b)
graph[b].append(a)の意味です。
#5
dist = [-1] * (n+1) #5
dist[0] = 0
dist[1] = 0dist(distanceの略)というリストを作成します。後で(#7)dist[i]が頂点1から頂点iの最短距離を表すようにしますが、この段階では初期化だけ行っています。
前述した通りdist[0]には特に意味はありませんが、dist[1]は頂点1から頂点1の距離なので0と定義しておきます。この定義は後々使うので大事。
#6
d = deque() #6
d.append(1)でましたdeque構造。まあぶっちゃけdequeを使わないで単純にリストにしてもできるんですが、今回dに対して「先頭から要素を取り出す」「末尾に要素を追加する」操作しか行わないので、先頭や最後の要素に対するアクセスがO(1)で行えるdequeを使いました(リストはO(n)です)。
この問題では頂点1からの最短距離を求めたいので、最初に頂点1を訪問してそこから他の頂点に向けて出発すると考えることができます。
dequeの使い方はリストに似ており、2行目のd.append(1)は「dの末尾に1を追加する」の意です。dには「新しく訪問した頂点を末尾に追加する」もしくは「先頭から過去に訪問した頂点を取り出す」という操作を繰り返す(#7)のですが、つまりここでd.append(1)を行うというのは、「頂点1を訪問した」という意味を持つわけです。
ここで覚えておきたいのが、dには上のような操作を繰り返すので、「頂点jがdの要素(dに入っている)」ならば、それは「頂点jは既に訪問済」であることを表すということです。
#7
今回の実装の要となる部分です。今まで定義してきたgraph, dist, dを用いてBFSを実装していきます。
以下に書いた説明だけでは理解が難しい人もいると思うので、私が参考にした記事を再掲しておきます。記事はこちら。
(以下の説明は上記の記事で詳しく解説されているBFSの概念的な部分には触れずアルゴリズム的な話に終始しているので、上記の記事→以下の説明、の順に読むことをおすすめします)
while d: #7
v = d.popleft()
for i in graph[v]:
if dist[i] != -1:
continue
dist[i] = dist[v] + 1
d.append(i)1行目のwhile文は一見意味がわかりませんが、「dがtrueの間は処理を続ける」、すなわち「dに1つ以上要素が入っているときに処理を続ける」ということです。#6より、dに1つも要素が入っていないというのは「過去に訪問した頂点を全て取り出した」、つまり全ての頂点に対して探索が終わっている状態を表すので、このwhile文を回せばいいことは自然なのではないでしょうか。
2行目のpopleft()はリストでいうpop(0)で、「最左端の要素を削除してその要素を取得する」メソッドです。vはdに入っていた要素なので、既に訪問済の頂点のうちの一つであるとわかります。
3～7行目に関しては以下のコメントアウトを参考にしてください。
while d:
v = d.popleft()
for i in graph[v]: #頂点vと直接つながっている頂点iに対して
if dist[i] != -1: #訪問済であれば
continue #スルーして次のiについて調べる
dist[i] = dist[v] + 1 #未訪問であれば左のように計算してdist[i]を決める
d.append(i) #今回新しく訪問した頂点iをdの末尾に追加3行目のfor i in graph[v]ってなに？for i in range()じゃないの？？という人はこちらをどうぞ。
4行目は、distの初期化(#5)でdist[0]とdist[1]以外は-1と定義したので、「dist[i] == 1であれば未訪問(このwhile文の中でまだ頂点iについて調べていない)」ということです。逆にdist[i] != 1なら訪問済であることを表します。
5行目のcontinue文は「このiは訪問済の頂点なので次のiを探す」という意味です。break文と混ざるやつですね。continue文についてはこちら。
6行目がこの実装全体の根幹部分です。既に訪問済である頂点vに対して、6行目まで到達したということは(= 5行目のcontinueで次のiに行かなかったということは)頂点iはまだ訪問していない頂点ということになります。iはgraph[v]の要素なので「頂点vと頂点iは直接つながっている」ことがわかりますが、iにはまだ訪問していません。これは「頂点1から頂点vまでの最短距離より頂点1から頂点iまでの最短距離の方が長い」ということを意味します。これが実際にどのくらい長いかは不明……なんですが、最短距離なので、まずは「頂点1から頂点vまでの最短距離(dist[v])より頂点1から頂点iまでの距離の方が1長い」ようなルートがあれば、それは確実に「頂点1から頂点iまでの最短距離(dist[i])」となりますよね。実際、今vとiは直接つながっているので、「頂点1から頂点vまで最短で行って、その次に頂点vと頂点iをつなぐ辺を通る」ことが実現できて、これが頂点iに到達する最短のルートになります。そして上の文から分かる通り、
dist[i] = dist[v] + 1とdist[i]を定義することができます。
たとえば、#5でdist[1]を0と定義しましたが、頂点1と頂点2が直接つながっているとしましょう。すると
dist[2] = dist[1] + 1 #dist[1] = 0 なので dist[2] = 1とわかります。頂点2は頂点1と直接つながっているのでdist[2] = 1は当たり前な感じがしますが、これはdist[1] = 0と最初に定義したことから導けた結論です。なにはともあれ、直観と合う結果が出たのではないでしょうか。
7行目は、今distが定義できたiをd(deque構造でしたね)の末尾に追加することで、次は頂点iと直接つながっている(かつ未訪問の)頂点を調べるのに使います。
この辺りはけっこう難しいと思います。よく分からなくなってきた人は、実際に紙とペンを使って実行例を手で再現してみることをおすすめします。
#8
ans = dist[1:] #8
print(*ans, sep="\n")出力の部分です。dist[0]は出力には不要なのでスライスすることで消してansという新しいリストにしています。最後の行ではリストのアンパックをしているのですが、要するにやっていることは↓と同じです。
for i in range(len(ans)):
print(ans[i])スライスについてわかりやすい記事はこちら
アンパックについて詳しくはこちら(詳しすぎて初心者向けではないかも)
あとがき
これでめでたく「Pythonを使って」「自力で」BFSを実装することができました🎉🎉🎉
*collectionsライブラリのdequeを使っていることが不満な方はリストで実装してみてください。計算量のオーダーこそ変わりますが、コード自体はほぼ変わらずに書けます。
できる限り丁寧に書いていたらいつのまにか7500字以上の大作になっていたようです。最後まで読んでくださった方、本当にありがとうございます。
編集履歴
2020.06.27 隣接リストに関する記述を追加。
2021.05.06 可読性のため表現や文章構成を変更、重複する文言を削除。参考:現在25いいね
最後まで読んでいただきありがとうございます。またどうぞ。
この記事が気に入ったらサポートをしてみませんか？