幅優先探索 - taq225's Memo on Algorithms

幅優先探索

Abstract近場から手堅くいくやつ.

$ O(|V| + |E|)timeのグラフ走査のアルゴリズム. 幅優先探索 (Breadth First Search: BFS) のテンプレートを書いた.

Explanation

TODO 書く.

Implementation

キューを利用することでBFSができる. Pythonではデック (deque)を利用して実装すればよい.

Input

グラフ (頂点は0-indexed) の隣接リスト E

BFSの始点 s

Output

BFSの探索順序 order

BFS木での親 parent

BFS木における深さ depth

Time complexity

$ O(|V| + |E|)time.

code:python

from collections import deque

def bfs(E, s):

N = len(E)

order = -1 * N # a bfs ordering of each vertex

parent = -1 * N # parent of each vertex in the bfs search tree

depth = -1 * N # the depth of each vertex

q = deque((s, -1, 0)) # (vertex, parent, depth)

num = 0 # current ordering

while q:

v, p, d = q.popleft()

if orderv < 0: # visited v for the first time

orderv = num; parentv = p; depthv = d

num += 1

for u in Ev:

if orderu >= 0: continue

q.append((u, v, d+1))

return order, parent, depth

Verification

特になし

References

特になし