幅優先探索(bfs)のpythonでの実装

DFS,BFS

・参考：
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 - Qiita

・内容：上の記事を参考にpythonでBFSを書いた。queueはcollectionsのdequeのほうが早いらしい。dequeはque=deque() #que.append(i)でappend,que.popleft()で左を取り出してキューから左の要素が消える。
queueはque=queue.Queue() #que.put(i),que.get()で同じことができる。

・実装：頂点0からの距離distを求めるもの。

from collections import deque
import queue
N,M=map(int,input().split()) #頂点数と辺の数

G=[[] for _ in range(M)]

for _ in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
  G[b].append(a)

dist=[-1 for _ in range(N)]  #未探索なら-1
#que=deque()  
que=queue.Queue()  

dist[0]=0
que.put(0)

while que.qsize()!=0:
  v=que.get()

  #vからいけるところがnv
  for nv in G[v]:
    if dist[nv]!=-1: 
      continue
    dist[nv]=dist[v]+1    
    que.put(nv)

for i in range(N):
  print(i,dist[i])