概要

グラフ\(G = (V, E)\)において、辺のコストが全て1である場合、BFSで探索することで、1頂点から各頂点までの距離を線形オーダーで探索できる。

計算量

\(O(N)\)

実装

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

Verified

  • AOJ: "ALDS1_11_C: Graph I - Breadth First Search": source (Python3, 0.03sec)