幅優先探索 (Breadth First Search)

概要

単一始点最短経路問題(SSSP)を解くアルゴリズム。

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

計算量

\(O(|V| + |E|)\)

実装

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
# s: 開始頂点
from collections import deque

def bfs(N, G, s):
    dist = [-1] * N
    que = deque([s])
    dist[s] = 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)

戻る