Algoritmo de busca em largura que explora o grafo nível por nível, encontrando o caminho mais curto em grafos sem peso.
BFS (Breadth-First Search) explora um grafo nível por nível, como ondas se espalhando em um lago. Primeiro visita todos os vizinhos diretos, depois os vizinhos dos vizinhos, e assim por diante. A chave do BFS é usar uma FILA (queue) em vez de pilha. A fila garante que vértices descobertos primeiro sejam processados primeiro (FIFO). Isso naturalmente resulta em exploração por níveis de distância. Por explorar nível por nível, BFS encontra automaticamente o caminho mais curto (em número de arestas) entre dois vértices em grafos sem peso. Esse é o motivo pelo qual é usado em GPS para encontrar rotas e em jogos para pathfinding em grids.
“A fila FIFO garante que vértices mais próximos da origem sejam sempre processados antes dos mais distantes, resultando em exploração por níveis e caminho mínimo.”
Cada vértice é enfileirado uma vez, e cada aresta é examinada uma vez.
O conjunto visited garante que cada vértice entra na fila apenas uma vez. Para cada vértice desenfileirado, iteramos sobre suas arestas adjacentes.
A fila pode conter até todos os vértices no pior caso (grafo estrela).
Se o destino é o próprio vértice inicial.
Quando precisamos visitar todo o grafo.
| Algoritmo | Tempo | Espaco | Melhor Para |
|---|---|---|---|
| BFS(atual) | O(V + E) | O(V) | Caminho mais curto em grafos sem peso, níveis de distância |
| DFS | O(V + E) | O(V) | Detecção de ciclos, ordenação topológica |
| Dijkstra | O((V+E) log V) | O(V) | Caminho mais curto com pesos positivos |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1from collections import dequeInicializar Fila2 3 4def bfs(graph, start):Definição5 visited = {start}Conjunto Visitados6 queue = deque([start])Inicializar Fila7 result = []8 9 while queue:Loop Principal10 vertex = queue.popleft()Desenfileirar11 result.append(vertex)Processar Vértice12 13 for neighbor in graph[vertex]:Enfileirar14 if neighbor not in visited:Verificar Visitado15 visited.add(neighbor)Marcar Visitado16 queue.append(neighbor)Enfileirar17 18 return result19 20 21def bfs_with_distance(graph, start):Definição22 visited = {start}Conjunto Visitados23 queue = deque([(start, 0)])Inicializar Fila24 distances = {start: 0}Rastrear Distância25 26 while queue:Loop Principal27 vertex, dist = queue.popleft()Desenfileirar28 29 for neighbor in graph[vertex]:Enfileirar30 if neighbor not in visited:Verificar Visitado31 visited.add(neighbor)Marcar Visitado32 distances[neighbor] = dist + 1Rastrear Distância33 queue.append((neighbor, dist + 1))Enfileirar34 35 return distances36