HowttaGraph Continuar aprendiendo
Visualizador · búsqueda en grafos

Rutas Paso a Paso

Elige un algoritmo y míralo trabajar sobre un mapa de 15 cruces. Cada paso resalta la línea de código que se está ejecutando, explica qué hace y muestra cómo cambian la cola, las distancias y los padres de cada nodo.

Lienzo

Grafo

Clic en un nodo fija:
Sin descubrir En la frontera Nodo actual Explorado Camino final Origen Destino
0 / 0
Qué está pasando

Código en Python

bfs()

clic en una línea = explicación

      
Línea

Estructura de datos

Cola (FIFO)

Bitácora

Historial de pasos

    Memoria del algoritmo

    Tabla de nodos

    La fila naranja cambió en este paso
    Mismo mapa, mismo origen y destino

    Comparativa de los cuatro

    Corremos los cuatro algoritmos sobre el grafo actual. Fíjate en cuántos nodos tuvo que explorar cada uno y si el camino que encontró es el más barato. Cambia el origen, el destino o genera otro grafo y la tabla se recalcula.

    Para estudiar

    Cómo piensa cada algoritmo

    Vocabulario

    Conceptos clave

    GrafoConjunto de nodos (vértices) unidos por aristas. Un mapa de calles es un grafo: los cruces son nodos y las calles son aristas.
    PesoCosto de recorrer una arista: distancia, tiempo o dinero. Aquí es el número en la etiqueta de cada calle.
    FronteraNodos ya descubiertos que todavía no se exploran. Vive en la cola, pila o cola de prioridad.
    PadreDesde qué nodo llegamos a otro. Siguiendo los padres hacia atrás desde el destino se reconstruye el camino.
    Relajar una aristaPreguntar si pasar por el nodo actual mejora la distancia conocida al vecino; si sí, se actualiza.
    Heurística h(n)Estimación de cuánto falta para llegar a la meta. A* usa la distancia en línea recta, que nunca sobreestima.
    AdmisibleUna heurística que nunca dice que falta más de lo que realmente falta. Con ella, A* garantiza encontrar el camino óptimo.
    ÓptimoEl camino de menor costo total posible entre origen y destino.