幅優先探索（Breadth First Search）

問題

次のような重みなし無向グラフに対して、頂点１から各頂点までの最短経路長を求めて下さい。

🔹頂点数は N、辺の数は M
🔹結びつく２つの頂点はリスト型に格納(edges変数)

[制約]
🔹1≦N≦100000
🔹0≦M≦min(100000,N(N−1)/2)
🔹1≦Ai<Bi≦N

解き方・ソースコード

この問題を幅優先探索で解いてきます。

幅優先探索は、スタートに近い頂点から順番に探索していくアルゴリズムです。

今回は、キューを使った方法で幅優先探索を行います。

手順は以下の通りです。

手順１：頂点 1 から頂点 x までの最短経路長の確定値を、dist[x]=−1 に初期化する。
手順２：キューに頂点 1 を追加し、dist[1]=0 にする。
手順３：キューが空になるまで、以下の手続きを繰り返す。
　🔹キューの先頭要素 pos を取得し、それをキューから削除する。
　🔹pos と隣接するすべての未確定頂点 to に対し、dist[to]=dist[pos]+1 を設定し、キューに to を追加する。
　　（未確定頂点とは dist[x]=−1 となっている頂点のことです。）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#-------- 入力例１ ---------
N = 6       # 頂点数
M = 5       # 辺の数
# 頂点同士のつながり情報
edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 6)]
#---------------------------
from collections import deque

# 隣接リストの作成
G = [ list() for i in range(N + 1) ]
for a, b in edges:
    G[a].append(b)
    G[b].append(a)

# 幅優先探索の初期化（dist[i] = -1 で初期化）
dist = [-1] * (N + 1)
dist[1] = 0
Q = deque()
Q.append(1)

# 幅優先探索
while len(Q) > 0:
    pos = Q.popleft() # キュー Q の先頭要素を取り除き、その値を pos に代入する
    for nex in G[pos]:
        if dist[nex] == -1: # まだチェックしてない頂点
            dist[nex] = dist[pos] + 1
            Q.append(nex)

# 頂点 1 から各頂点までの最短距離を出力
for i in range(1, N + 1):
    print('頂点 1 から頂点 {} までの最短経路は {}'.format(i, dist[i]))

[実行結果（入力例１）]

頂点 1 から頂点 1 までの最短経路は 0

頂点 1 から頂点 2 までの最短経路は 1

頂点 1 から頂点 3 までの最短経路は 1

頂点 1 から頂点 4 までの最短経路は 2

頂点 1 から頂点 5 までの最短経路は -1

頂点 1 から頂点 6 までの最短経路は 3

頂点１から各頂点への最短経路長を求めることができました。