Búsqueda en grafos: BFS y DFS
Recorrer grafos evitando ciclos con el registro de visitados: BFS con cola (camino más corto) y DFS con stack (iterativo y recursivo).
warning
Recorrer un grafo: el problema de los ciclos
Podemos recorrer un grafo con los mismos algoritmos que usamos en árboles (BFS y DFS), pero con un cuidado extra: los grafos pueden tener ciclos.
Un ciclo es una secuencia de nodos conectados que vuelve al punto de partida. Si recorremos sin control, el algoritmo vuelve a visitar nodos ya procesados y queda atrapado en un bucle infinito.
Esto no pasa en los árboles, porque hay una única ruta a cada nodo (a través de su padre). En un grafo general sí, por lo que es fundamental registrar los vértices ya visitados.
Sin un registro de visitados, un recorrido sobre un grafo con ciclos puede no terminar nunca. Marcar los nodos visitados es lo que garantiza que el algoritmo finalice.
Clave
Cargando Quiz...
hub
BFS: Breadth-First Search
BFS (búsqueda en amplitud) usa una cola (deque). Visita primero todos los nodos a una arista del inicial, luego los que están a dos aristas, y así sucesivamente: avanza por niveles de distancia.
python
from collections import deque def bfs(grafo, inicio): visitados = [] cola = deque([inicio]) while len(cola) > 0: vertice = cola.popleft() if vertice in visitados: continue visitados.append(vertice) for vecino in grafo[vertice]: if vecino not in visitados: cola.append(vecino) return visitadosComo recorre por niveles, BFS sirve para encontrar el camino más corto en número de aristas entre dos nodos (cuando todas las aristas pesan igual). Los nodos que no aparecen en el recorrido no son alcanzables desde el inicio.
Cargando Quiz...
Cargando Quiz...
schema
DFS iterativo
DFS (búsqueda en profundidad) explora una rama lo más lejos posible antes de devolverse y probar otra. Su implementación iterativa es casi idéntica a BFS, pero usa un stack (list con pop()) en vez de una cola.
python
def dfs(grafo, inicio): visitados = set() stack = [inicio] while len(stack) > 0: vertice = stack.pop() if vertice in visitados: continue visitados.add(vertice) for vecino in grafo[vertice]: if vecino not in visitados: stack.append(vecino)psychology
DFS recursivo
DFS tiene una implementación recursiva muy natural: se visita el vértice y se llama recursivamente sobre cada vecino no visitado. El conjunto visitados se pasa como parámetro para compartirlo entre llamadas.
python
def dfs_recursivo(grafo, vertice, visitados=None): visitados = visitados or set() visitados.add(vertice) for vecino in grafo[vertice]: if vecino not in visitados: dfs_recursivo(grafo, vecino, visitados) return list(visitados)La recursión usa implícitamente la pila de llamadas del programa como el stack que en la versión iterativa manejábamos a mano.
Tanto BFS como DFS retornan exactamente los nodos alcanzables desde el inicio. Si un nodo queda fuera del resultado, significa que no existe ningún camino hacia él desde el punto de partida.
Recuerda