幅優先探索(BFS) - プログラミング初心者の日記

今回は幅優先探索(BFS)をやっていきます。
幅優先探索は各頂点への最短経路を求めることのできるアルゴリズムですが、辺に移動距離や時間などを考慮しないため、使う際は注意が必要。
今回は以下のグラフを使います。
f:id:nasubiFX:20201027154438p:plain
頂点が8個、辺が8個のグラフです。
なので入力は以下のようになります

8 8 頂点の数、辺の数
0 1 頂点、隣接する頂点
0 2
1 3
1 4
2 4
2 5
4 6
4 7

まず、基本の処理から書いていきます。

from collections import deque

N,M=map(int,input().split())
Graph=[[] for _ in range(N)]

for i in range(M): #隣接リストを作成
    a,b=map(int,input().split())
    Graph[a].append(b)
    Graph[b].append(a)
    
dist=[-1]*(N) #頂点を訪問したか　初期値は全部未訪問
dist[0]=0 #頂点0から頂点0の距離は0
queue=deque() #キューを作成
queue.append(0) #頂点0から始める

dequeの使い方は下記サイトを参考にしました
https://note.nkmk.me/python-collections-deque/

今回は先頭の要素の削除、リストへの追加しか行わないのでdequeを使った方が効率が良いらしい。
普通にリストを書くことも可能。

distの役割は距離の格納と、訪問済みかの判断
値が-1なら未訪問で、それ以外なら頂点0からの距離が入っているので訪問済みと判断できる。

次に処理の部分を書いていきます

while queue: #キューが空になるまで
    v=queue.popleft() #キューから先頭要素を削除し、取り出す
    
    for i in Graph[v]:#頂点vの隣接する頂点をすべて調べる
        if dist[i] !=-1:#探索済みならスルー
            continue
        dist[i]=dist[v]+1 #隣接する頂点の距離は、現在の距離+1となる
        queue.append(i) #キューに次に調べる頂点を追加

dist[i]=dist[v]+1は、現在の頂点から隣接する頂点に行くための距離は辺がつながっているので必ず+1の距離で行くことができる。
例えば、頂点0から隣接する頂点1,2は頂点0から+1の距離で行くことができる。
なので、distの値はdist=[0,1,1]となる。
さらに、頂点1から隣接する頂点0,3,4は頂点1から+1の距離で行くことができるので現在の1に+1を足した2の距離で行くことができる。ただし、頂点0は探索済みなのでスルーする。
なので、distの値はdist=[0,1,1,2,2]となる。
このように距離が変化していく。
コード全体

from collections import deque

N,M=map(int,input().split())
Graph=[[] for _ in range(N)]

for i in range(M): #隣接リストを作成
    a,b=map(int,input().split())
    Graph[a].append(b)
    Graph[b].append(a)
    
dist=[-1]*(N) #頂点を訪問したか　初期値は全部未訪問
dist[0]=0 #頂点0から頂点0の距離は0
queue=deque() #キューを作成
queue.append(0) #頂点0から始める

while queue: #キューが空になるまで
    v=queue.popleft() #キューから先頭要素を削除し、取り出す
    
    for i in Graph[v]:#頂点vの隣接する頂点をすべて調べる
        if dist[i] !=-1:#探索済みならスルー
            continue
        dist[i]=dist[v]+1 #隣接する頂点の距離は、現在の距離+1となる
        queue.append(i) #キューに次に調べる頂点を追加
        
for j in range(N):
    print(j,dist[j])