BFS с пометкой посещения при извлечении: что именно ломается
from collections import deque
def bfs(graph, start):
order = []
q = deque([start])
visited = set()
while q:
node = q.popleft()
if node in visited:
continue
visited.add(node)
order.append(node)
for nxt in graph[node]:
q.append(nxt)
return order
Вершина помечается посещённой в момент извлечения из очереди, а не в момент добавления. Что это меняет?
- Обход зациклится, если в графе есть цикл: вершина будет добавляться в очередь бесконечно
- Нужно заменить deque на обычный list, иначе popleft на длинной очереди работает за линейное время
- Порядок обхода станет неверным: BFS требует пометки именно в момент добавления в очередь
- Порядок верный, но вершина попадает в очередь по разу на каждое входящее ребро — память до O(E)