Búsqueda en anchura (BFS)
Última actualización
La búsqueda en anchura explora un grafo nivel por nivel. Partiendo de un nodo origen, visita primero todos sus vecinos inmediatos, luego todos los vecinos no visitados de estos, y así sucesivamente - expandiéndose hacia afuera en anillos de distancia creciente. Pulsa reproducir arriba para verla abrirse desde el nodo inicial una capa a la vez.
BFS usa una cola de tipo primero en entrar, primero en salir, que es lo que impone el orden nivel por nivel. Como alcanza los nodos en orden de distancia en saltos, BFS encuentra el camino más corto (menos aristas) en un grafo no ponderado. Visita cada nodo y arista una vez, por lo que se ejecuta en tiempo O(V + E).
Complejidad temporal y espacial
| Medida | Complejidad | Notas |
|---|---|---|
| Tiempo | O(V + E) | Cada vértice y arista se visita una vez |
| Espacio | O(V) | Cola + conjunto de visitados, en el peor caso todos los nodos |
| Recorrido | Nivel por nivel | Los nodos más cercanos primero, en anillos |
| Camino más corto | Sí (no ponderado) | Alcanza cada nodo con menos aristas |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Encola el nodo origen. |
| 2 | Desencola el nodo del frente y márcalo como visitado. |
| 3 | Examina cada uno de sus vecinos. |
| 4 | Encola cualquier vecino que no esté ya visitado o en cola. |
| 5 | Repite hasta que la cola esté vacía. |
Ejemplo resuelto
Recorriendo este grafo desde el nodo 0, donde 0-1, 0-2, 1-3, 2-3, 2-4 son aristas:
| Paso | Visitados | Cola (frontera) |
|---|---|---|
| Inicio | {} | [0] |
Desencola 0 | {0} | [1, 2] |
Desencola 1 | {0, 1} | [2, 3] |
Desencola 2 | {0, 1, 2} | [3, 4] |
Desencola 3 | {0, 1, 2, 3} | [4] |
Desencola 4 | {0, 1, 2, 3, 4} | [] (fin) |
Cuándo usar BFS
| Úsalo cuando | Evítalo cuando |
|---|---|
| Necesitas el camino más corto en un grafo no ponderado | Las aristas tienen pesos - usa Dijkstra en su lugar |
| Es probable que el objetivo esté cerca del origen | El grafo es muy ancho - la cola puede contener una frontera enorme |
| Quieres explorar un grafo en orden por niveles | Solo necesitas alcanzar cualquier nodo, donde DFS usa menos memoria |
| Buscas componentes conexas o una ruta de mínimos saltos | Necesitas ordenamiento topológico o detección de ciclos - DFS encaja mejor |
Código de Breadth-First Search
Una implementación limpia y ejecutable de Breadth-First Search en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Breadth-First Search en 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 en 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 en 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 en 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 en 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}Preguntas frecuentes sobre la búsqueda en anchura
¿Cuál es la complejidad temporal de BFS?
O(V + E), donde V es el número de vértices y E el de aristas, ya que visita cada vértice una vez y examina cada arista una vez. Usa O(V) de espacio para la cola y el conjunto de visitados.¿Encuentra BFS el camino más corto?
Sí, en un grafo no ponderado. Como BFS alcanza los nodos en orden de distancia en saltos desde el origen, la primera vez que llega a un nodo es por un camino con menos aristas. Para grafos ponderados necesitas el algoritmo de Dijkstra.
¿Cuál es la diferencia entre BFS y DFS?
BFS usa una cola y explora nivel por nivel (los más cercanos primero), mientras que DFS usa una pila y se adentra por una rama antes de retroceder. BFS encuentra los caminos más cortos no ponderados; DFS usa menos memoria en grafos anchos y sirve para detección de ciclos y ordenamiento topológico.
¿Cuándo debo usar BFS en lugar del algoritmo de Dijkstra?
O(V + E) sin una cola de prioridad. El algoritmo de Dijkstra es necesario cuando las aristas tienen pesos distintos; ejecutar BFS puro en un grafo ponderado da el camino de menos saltos, no el de menor costo.¿Por qué BFS necesita un conjunto de visitados?
Los grafos pueden contener ciclos, así que sin un conjunto de visitados BFS encolaría el mismo nodo repetidamente y entraría en un bucle infinito. Marcar un nodo cuando lo encolas por primera vez (no al desencolarlo) también evita que el mismo nodo se añada a la cola dos veces por vecinos distintos.
¿Debo marcar un nodo como visitado al encolarlo o al desencolarlo?
Márcalo al encolarlo. Si esperas hasta desencolarlo, un nodo puede ser añadido a la cola varias veces por vecinos distintos antes de procesarse, desperdiciando memoria y tiempo. Marcarlo al encolar garantiza que cada nodo entra a la cola exactamente una vez.
Recursos relacionados
Más visualizaciones
