Busca em largura (BFS)
Última atualização
A busca em largura explora um grafo nível por nível. Partindo de um nó de origem, ela visita primeiro todos os seus vizinhos imediatos, depois todos os vizinhos não visitados destes, e assim por diante - expandindo-se para fora em anéis de distância crescente. Pressione reproduzir acima para vê-la se abrir a partir do nó inicial uma camada de cada vez.
A BFS usa uma fila do tipo primeiro a entrar, primeiro a sair, que é o que impõe a ordem nível por nível. Como alcança os nós em ordem de distância em saltos, a BFS encontra o caminho mais curto (menos arestas) em um grafo não ponderado. Ela visita cada nó e aresta uma vez, então roda em tempo O(V + E).
Complexidade de tempo e espaço
| Medida | Complexidade | Observações |
|---|---|---|
| Tempo | O(V + E) | Cada vértice e aresta visitado uma vez |
| Espaço | O(V) | Fila + conjunto de visitados, no pior caso todos os nós |
| Travessia | Nível por nível | Os nós mais próximos primeiro, em anéis |
| Caminho mais curto | Sim (não ponderado) | Alcança cada nó com menos arestas |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Enfileira o nó de origem. |
| 2 | Desenfileira o nó da frente e marca-o como visitado. |
| 3 | Examina cada um dos seus vizinhos. |
| 4 | Enfileira qualquer vizinho que ainda não esteja visitado ou na fila. |
| 5 | Repete até a fila ficar vazia. |
Exemplo resolvido
Percorrendo este grafo a partir do nó 0, onde 0-1, 0-2, 1-3, 2-3, 2-4 são arestas:
| Passo | Visitados | Fila (fronteira) |
|---|---|---|
| Início | {} | [0] |
Desenfileira 0 | {0} | [1, 2] |
Desenfileira 1 | {0, 1} | [2, 3] |
Desenfileira 2 | {0, 1, 2} | [3, 4] |
Desenfileira 3 | {0, 1, 2, 3} | [4] |
Desenfileira 4 | {0, 1, 2, 3, 4} | [] (fim) |
Quando usar a BFS
| Use quando | Evite quando |
|---|---|
| Você precisa do caminho mais curto em um grafo não ponderado | As arestas têm pesos - use Dijkstra em vez disso |
| O alvo provavelmente está perto da origem | O grafo é muito largo - a fila pode conter uma fronteira enorme |
| Você quer explorar um grafo em ordem por níveis | Você só precisa alcançar qualquer nó, onde a DFS usa menos memória |
| Você busca componentes conexos ou uma rota de mínimos saltos | Você precisa de ordenação topológica ou detecção de ciclos - a DFS encaixa melhor |
Código de Breadth-First Search
Uma implementação limpa e executável de Breadth-First Search em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Breadth-First Search em Python
Python
1from collections import deque2
3
4def bfs(graph, start):5 visited = {start}6 queue = deque([start])7 order = []8 while queue:9 node = queue.popleft()10 order.append(node)11 for neighbor in graph[node]:12 if neighbor not in visited:13 visited.add(neighbor) # mark on enqueue, not dequeue14 queue.append(neighbor)15 return order16
17
18graph = {19 "A": ["B", "C"],20 "B": ["D", "E"],21 "C": ["F"],22 "D": [],23 "E": ["F"],24 "F": [],25}26
27print("BFS order:", " -> ".join(bfs(graph, "A")))Código de Breadth-First Search em JavaScript
JavaScript
1const graph = {2 A: ["B", "C"],3 B: ["D", "E"],4 C: ["F"],5 D: [],6 E: ["F"],7 F: [],8};9
10function bfs(start) {11 const visited = new Set([start]);12 const queue = [start];13 const order = [];14 while (queue.length > 0) {15 const node = queue.shift(); // Dequeue the oldest node16 order.push(node);17 for (const next of graph[node]) {18 if (!visited.has(next)) {19 visited.add(next);20 queue.push(next);21 }22 }23 }24 return order;25}26
27console.log("BFS from A:", bfs("A").join(" -> "));Código de Breadth-First Search em Java
Java
1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6 public static void main(String[] args) {7 List<List<Integer>> adj = List.of(8 List.of(1, 2), // neighbors of 09 List.of(0, 3, 4), // neighbors of 110 List.of(0, 5),11 List.of(1),12 List.of(1, 5),13 List.of(2, 4)14 );15 boolean[] visited = new boolean[adj.size()];16 Queue<Integer> queue = new ArrayDeque<>();17 visited[0] = true;18 queue.add(0);19
20 StringBuilder order = new StringBuilder("BFS from 0:");21 while (!queue.isEmpty()) {22 int node = queue.poll();23 order.append(" ").append(node);24 // Mark neighbors when enqueued so nothing enters twice25 for (int next : adj.get(node)) {26 if (!visited[next]) {27 visited[next] = true;28 queue.add(next);29 }30 }31 }32 System.out.println(order);33 }34}Código de Breadth-First Search em C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5void bfs(int start, const std::vector<std::vector<int>>& adj) {6 std::vector<bool> visited(adj.size(), false);7 std::queue<int> frontier;8 visited[start] = true;9 frontier.push(start);10 // Visit nodes level by level11 while (!frontier.empty()) {12 int node = frontier.front();13 frontier.pop();14 std::cout << node << " ";15 for (int next : adj[node]) {16 if (!visited[next]) {17 visited[next] = true;18 frontier.push(next);19 }20 }21 }22}23
24int main() {25 // 6-node undirected graph as an adjacency list26 std::vector<std::vector<int>> adj = {27 {1, 2}, // 028 {0, 3, 4}, // 129 {0, 5}, // 230 {1}, // 331 {1, 5}, // 432 {2, 4}, // 533 };34 std::cout << "BFS from node 0: ";35 bfs(0, adj);36 std::cout << "\n";37 return 0;38}Código de Breadth-First Search em C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6void bfs(int start, const int adj[N][N]) {7 bool visited[N] = {false};8 int queue[N]; // fixed-size queue: head chases tail9 int head = 0, tail = 0;10 visited[start] = true;11 queue[tail++] = start;12 // Visit nodes level by level13 while (head < tail) {14 int node = queue[head++];15 printf("%d ", node);16 for (int next = 0; next < N; next++) {17 if (adj[node][next] && !visited[next]) {18 visited[next] = true;19 queue[tail++] = next;20 }21 }22 }23}24
25int main(void) {26 // 6-node undirected graph as an adjacency matrix27 int adj[N][N] = {28 {0, 1, 1, 0, 0, 0},29 {1, 0, 0, 1, 1, 0},30 {1, 0, 0, 0, 0, 1},31 {0, 1, 0, 0, 0, 0},32 {0, 1, 0, 0, 0, 1},33 {0, 0, 1, 0, 1, 0},34 };35 printf("BFS from node 0: ");36 bfs(0, adj);37 printf("\n");38 return 0;39}Perguntas frequentes sobre a busca em largura
Qual é a complexidade de tempo da BFS?
A BFS roda em tempo
O(V + E), onde V é o número de vértices e E o de arestas, pois visita cada vértice uma vez e examina cada aresta uma vez. Ela usa O(V) de espaço para a fila e o conjunto de visitados.A BFS encontra o caminho mais curto?
Sim, em um grafo não ponderado. Como a BFS alcança os nós em ordem de distância em saltos a partir da origem, a primeira vez que chega a um nó é por um caminho com menos arestas. Para grafos ponderados você precisa do algoritmo de Dijkstra.
Qual é a diferença entre BFS e DFS?
A BFS usa uma fila e explora nível por nível (os mais próximos primeiro), enquanto a DFS usa uma pilha e mergulha por um ramo antes de retroceder. A BFS encontra os caminhos mais curtos não ponderados; a DFS usa menos memória em grafos largos e serve para detecção de ciclos e ordenação topológica.
Quando devo usar a BFS em vez do algoritmo de Dijkstra?
Use a BFS quando todas as arestas têm o mesmo custo, pois ela encontra o caminho com menos arestas em tempo
O(V + E) sem uma fila de prioridade. O algoritmo de Dijkstra é necessário quando as arestas têm pesos diferentes; rodar BFS pura em um grafo ponderado dá o caminho de menos saltos, não o de menor custo.Por que a BFS precisa de um conjunto de visitados?
Grafos podem conter ciclos, então sem um conjunto de visitados a BFS enfileiraria o mesmo nó repetidamente e entraria em um laço infinito. Marcar um nó quando você o enfileira pela primeira vez (não ao desenfileirá-lo) também evita que o mesmo nó seja adicionado à fila duas vezes por vizinhos diferentes.
Devo marcar um nó como visitado ao enfileirar ou ao desenfileirar?
Marque-o ao enfileirar. Se você esperar até desenfileirá-lo, um nó pode ser adicionado à fila várias vezes por vizinhos diferentes antes de ser processado, desperdiçando memória e tempo. Marcar ao enfileirar garante que cada nó entra na fila exatamente uma vez.
Recursos relacionados
Mais visualizações
