Informática / GrafosA tu ritmo
Encuentra el camino.
Entiende cada decisión.
BFS, DFS, Dijkstra y A* sobre el mismo grafo. Sigue la búsqueda y descubre qué significa elegir el mejor camino.
BFS
Primero, los más cercanos en conexiones.
Empezamos en el origen. Avanza para ver cómo se elige el siguiente nodo.
AEncuentra un camino con el menor número de conexiones. Si los costes son distintos, eso no garantiza el menor coste.
Cambiar conexiones y costesPrueba tus propios casos
Guardar actualiza una conexión existente o crea una nueva. Ambas direcciones tienen el mismo coste. Puedes usar coste 0; no se admiten costes negativos.
A — B8B — D6D — H8A — C2C — E2E — G2G — H2B — E5D — F2F — H3E — F4
Ver costes y padresEstado en este paso
| Nodo | Conexiones | Padre |
|---|---|---|
| A | 0 | — |
| B | ∞ | — |
| C | ∞ | — |
| D | ∞ | — |
| E | ∞ | — |
| F | ∞ | — |
| G | ∞ | — |
| H | ∞ | — |
Comparar los cuatro algoritmosEl mismo origen y destino
| Algoritmo | Camino | Conexiones | Coste | Nodos |
|---|---|---|---|---|
| BFS | A → B → D → H | 3 | 22 | 7 |
| DFS | A → B → D → F → E → G → H | 6 | 24 | 8 |
| Dijkstra | A → C → E → G → H | 4 | 8 | 7 |
| A* | A → C → E → G → H | 4 | 8 | 5 |
Nodos = selecciones realizadas hasta encontrar el destino o agotar la búsqueda. No mide tiempo. BFS minimiza conexiones; Dijkstra y A* minimizan coste. DFS depende del orden de vecinos.
BFS: Primero, los más cercanos en conexiones.
Visita por capas. Primero los vecinos del origen, después los vecinos de esos vecinos. Marca cada nodo al añadirlo a la cola para no repetirlo.
Una cola: el primero en entrar es el primero en salir.
Qué garantiza
Encuentra un camino con el menor número de conexiones. Si los costes son distintos, eso no garantiza el menor coste.
cola ← [origen]
mientras la cola no esté vacía:
u ← sacar el primero
si u = destino: devolver camino
para cada vecino v no descubierto:
padre[v] ← u; marcar v; añadir al finalLos vecinos se revisan por orden alfabético. Dijkstra y A* también rompen empates por letra. Esto hace reproducible el recorrido; puede haber otros caminos igual de buenos.
Tiempo y memoria
Con listas de adyacencia, BFS y DFS recorren como máximo V nodos y E conexiones: O(V + E), con O(V) de memoria auxiliar.
Para que puedas inspeccionar los pasos, este laboratorio ordena un array de prioridades y guarda copias del estado. No es una implementación optimizada para medir rendimiento.
Ahora decide tú.
Un caso distinto al del explorador. Primero predice el nodo; después, explica la decisión.
BC