幅優先探索（BFS）とは
幅優先探索（BFS / 横型探索）とは - 意味をわかりやすく - IT用語辞典 e-Words
使い所
最短経路問題
ソースコード
経路復元と距離計測もあり。
・経路復元は何をしているのか？
配列を辿っていっている。
例：配列A A[現在地] = 次の目的地
- A[5] = 3：現在地＝5。次の目的地３なので、A[3]に移動
- A[3] = 1：現在地＝3。次の目的地1なので、A[1]に移動
- A[1] = 0：現在地＝1。次の目的地0なので、A[0]に移動
- A[0]：0に到着
from collections import deque n = int(input()) g=[[] for _ in range(n)] Q=deque() seen=[False]*n #探索済チェック用 dist=[0]*n #距離計測用 previous =[0]*n #探索経路用 #入力の受け取り for i in range(n-1): u,v=map(int,input().split()) u=u-1 v=v-1 g[u].append(v) g[v].append(u) Q.append(0)#始点をキューに追加 previous[0] = -2 #始点には-2 while(len(Q)) > 0: vertex = Q.popleft() #先入れ先出し #vertex = Q.pop #後入れ先出し seen[vertex] = True for next in g[vertex]: if seen[next]: continue #探索済みはスルー dist[next] = dist[vertex] + 1 #距離を格納 #探索経路を1つ前の頂点を追加 previous[next] = vertex Q.append(next)#キューに次を追加 ans = [] now = 5 #頂点5から始点までの最短経路復元 ans.append(now - 1) while previous[now] != -2: now = previous[now] ans.append(now + 1) # 最短経路を出力 print(*ans[::-1])
