Pseudo Code
Урок 4 из 9 курса Поиск в ширину — Алгоритмы на графах на Coddy.
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 заключается в контейнере: очередь (FIFO) вместо стека (LIFO).
- Простой способ реализовать очередь — это массив с движущимся индексом head: извлечение (dequeue) происходит путем чтения
queue[head]и сдвигаhead.
Попробуйте сами
В этом уроке нет задания по программированию.
В этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Поиск в ширину — Алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)