Pseudo Code
Coddyの「幅優先探索 - グラフアルゴリズム」コースのレッスン 4/9。
bfs(n, edges, start):
build adjacency (sort each list ascending)
visited = all false
queue = [start]; visited[start] = true
order = []
while queue not empty:
node = queue.dequeue() # 先頭から取り出す
order.add(node)
for nb in adj[node]:
if not visited[nb]:
visited[nb] = true
queue.enqueue(nb)
return order- DFSとの唯一の違いはコンテナです。スタック（LIFO）の代わりにキュー（FIFO）を使用します。
- キューを実装する簡単な方法は、移動するheadインデックスを持つ配列を使用することです。
queue[head]を読み取ってheadを進めることでデキューを行います。
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
幅優先探索 - グラフアルゴリズムのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity