Skip to main content

Abrir el simulador

BFS, DFS y Dijkstra paso a paso: frontera, orden de visita, distancias y camino más corto.
Un mapa de carreteras, una red social, Internet o las dependencias entre las asignaturas de una carrera son grafos: nodos unidos por aristas. Recorrerlos de forma sistemática permite encontrar caminos, detectar ciclos o calcular la ruta más corta, como hace un GPS.

​
Lo que vas a aprender

  • Qué es un grafo y cómo se representa.
  • La búsqueda en anchura (BFS) y en profundidad (DFS).
  • El algoritmo de Dijkstra para caminos más cortos con pesos.
  • Cuándo usar cada uno y su coste.

​
Cómo se usa el simulador

  • Elige el algoritmo: BFS, DFS o Dijkstra. 🎲 Grafo aleatorio genera otro grafo.
  • Elige el origen (o pulsa un nodo del grafo) y, en Dijkstra, el destino.
  • Avanza con ⏮, ▶ Recorrer y ⏭, y ajusta la velocidad.
  • Los colores marcan la frontera (nodos pendientes) y los visitados. A la derecha se ven la cola, la pila o la cola de prioridad, y la tabla de distancias con el nodo del que viene cada uno.

​
Fundamentos teóricos

​
Grafos

Un grafo G=(V,E)G = (V, E) tiene vértices (nodos) y aristas. Puede ser dirigido o no, y las aristas pueden tener pesos (distancias, costes, tiempos). Se representa con una matriz de adyacencia o con listas de adyacencia.

​
BFS: búsqueda en anchura

Usa una cola. Visita primero los vecinos del origen, luego los vecinos de esos, y así por capas.
Encuentra el camino con menos aristas desde el origen.

​
DFS: búsqueda en profundidad

Usa una pila (o recursión). Sigue un camino hasta el fondo antes de volver atrás. Usos: detectar ciclos, orden topológico de tareas con dependencias, componentes conexas, laberintos.

​
Dijkstra

Para caminos más cortos con pesos no negativos:
  1. Distancia del origen: 0; del resto: ∞.
  2. Saca de la cola de prioridad el nodo pendiente con menor distancia: esa distancia ya es definitiva.
  3. Para cada vecino, si llegar a través de él es más corto, actualiza su distancia (relajación).
  4. Repite hasta vaciar la cola.
No funciona con pesos negativos (para eso está Bellman-Ford).

​
Coste

​
Ejemplos resueltos

Ejemplo 1 · Dijkstra

Grafo: A–B (4), A–C (1), C–B (2), B–D (5), C–D (8). Camino más corto de A a D.
  1. A = 0. C = 1, B = 4.
  2. Se fija C (1): B mejora a 3; D = 9.
  3. Se fija B (3): D mejora a 8.
  4. Se fija D (8).
Camino: A → C → B → D, distancia 8.
En un grafo donde A está unido a B y C, B a D, y C a D y E, BFS desde A visita: A; B, C; D, E. D queda a 2 aristas.

​
Experimenta con el simulador

1

BFS frente a DFS

Recorre el mismo grafo con BFS y con DFS desde el mismo origen. ¿Cambia el orden de visita?
2

La frontera

Mira la cola en BFS y la pila en DFS. ¿Cuál crece más?
3

Relajación

En Dijkstra, fíjate en las distancias que mejoran durante el recorrido.

​
Errores frecuentes

  • No marcar los nodos visitados: el recorrido entra en bucle.
  • Usar BFS para caminos con pesos: solo minimiza el número de aristas.
  • Fijar un nodo en Dijkstra antes de que sea el mínimo de la cola.

​
Herramientas relacionadas

Estructuras de datos

Pilas y colas.

Backtracking

Explorar todas las posibilidades.

Recursión

DFS recursivo.
Última modificación el 6 de octubre de 2026