BFS — O(V+E)
Explora camada por camada usando uma Fila.
Tempo: O(V + E) — visita cada vertice e aresta uma vez
Espaco: O(V) — set visited + fila
Encontra caminho mais curto em grafos sem peso!
Tempo: O(V + E) — visita cada vertice e aresta uma vez
Espaco: O(V) — set visited + fila
Encontra caminho mais curto em grafos sem peso!
Python
from collections import deque def bfs(graph, start): visited = set([start]) queue = deque([start]) result = [] while queue: node = queue.popleft() result.append(node) for nb in graph[node]: if nb not in visited: visited.add(nb) queue.append(nb) return result