> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

# Recorridos de grafos: BFS, DFS y algoritmo de Dijkstra

> Grafos explicados: búsqueda en anchura (BFS) con cola, búsqueda en profundidad (DFS) con pila y algoritmo de Dijkstra para caminos más cortos con pesos, con pseudocódigo, coste y ejemplos.

<Card title="Abrir el simulador" icon="flask" href="https://simulab.es/programacion/grafos">
  BFS, DFS y Dijkstra paso a paso: frontera, orden de visita, distancias y camino más corto.
</Card>

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)$ 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**.

```text theme={null}
encolar(origen); marcar(origen)
mientras la cola no esté vacía:
    u = desencolar()
    para cada vecino v de u no marcado:
        marcar(v); padre[v] = u; encolar(v)
```

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

| Algoritmo | Coste (listas de adyacencia) |
| - | - |
| BFS, DFS | $O(V + E)$ |
| Dijkstra con montículo | $O((V + E)\log V)$ |

## Ejemplos resueltos

<AccordionGroup>
  <Accordion title="Ejemplo 1 · Dijkstra" defaultOpen>
    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.
  </Accordion>

  <Accordion title="Ejemplo 2 · BFS por capas">
    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.
  </Accordion>
</AccordionGroup>

## Experimenta con el simulador

<Steps>
  <Step title="BFS frente a DFS">
    Recorre el mismo grafo con BFS y con DFS desde el mismo origen. ¿Cambia el orden de visita?
  </Step>

  <Step title="La frontera">
    Mira la cola en BFS y la pila en DFS. ¿Cuál crece más?
  </Step>

  <Step title="Relajación">
    En Dijkstra, fíjate en las distancias que mejoran durante el recorrido.
  </Step>
</Steps>

## 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

<CardGroup cols={3}>
  <Card title="Estructuras de datos" icon="layer-group" href="/programacion/algoritmos/estructuras-datos">
    Pilas y colas.
  </Card>

  <Card title="Backtracking" icon="code-branch" href="/programacion/c/backtracking">
    Explorar todas las posibilidades.
  </Card>

  <Card title="Recursión" icon="arrows-rotate" href="/programacion/c/recursion">
    DFS recursivo.
  </Card>
</CardGroup>


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.