¿Cómo hallas el camino más corto (menos aristas) en un grafo sin pesos?
Opciones
- DFS
- BFS (Opción correcta)
- Dijkstra con un max-heap
- Ordenación topológica
Respuesta
BFS
Por qué
BFS (breadth-first search, búsqueda en anchura) explora en anillos: primero todos los vecinos a 1 paso, luego todos a 2 pasos, y así sucesivamente, con una cola.
Así que la primera vez que BFS llega a un nodo, lo hizo con las menos aristas posibles.
DFS profundiza primero por un camino, así que el primer camino que encuentra puede ser largo. Coste de BFS: O(V + E).
Recuerda
Menos pasos en un grafo sin pesos → BFS.