幅優先探索（Breadth First Search）

問題

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

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

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 0 \leqq M \leqq min(100000,N(N-1)/2) $
🔹$ 1 \leqq A_i < B_i \leqq 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

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