Construye el grafo, elige el algoritmo y sigue cada paso de la ejecución.
Un laboratorio visual para clases y tutorías. Dibuja vértices y aristas dirigidas o no dirigidas, define pesos y ejecuta los algoritmos clásicos de la asignatura con la misma notación usada en clase, con tablas, colas y la justificación de cada iteración.
Edición directa en el lienzo
Crea vértices con un clic, conéctalos y ajusta pesos y dirección sin salir de la pantalla.
Dirigido, no dirigido o mixto
Cada arista guarda su propia orientación. Los algoritmos validan el tipo de grafo requerido antes de ejecutarse.
Traza paso a paso
Colas, pilas, tablas de dist y pred y matrices de distancia acompañan la animación en cada iteración.
De la búsqueda en grafos a la coloración, en el orden de la asignatura
Cada ejecución genera una traza completa: marcado de los vértices, tablas auxiliares y la justificación de cada decisión.
Búsqueda en profundidad
O(n + m)Elige siempre el vértice marcado alcanzado más recientemente y registra un tiempo de descubrimiento TD y un tiempo de finalización TF.
Búsqueda en grafos
Búsqueda en anchura
O(n + m)Elige siempre el vértice marcado alcanzado hace más tiempo, usando una cola, y asigna a cada vértice su nivel.
Búsqueda en grafos
Algoritmo de Kosaraju
O(n + m)Encuentra las componentes fuertemente conexas con dos búsquedas en profundidad: una en G y otra en el grafo inverso Gᴿ.
Conectividad
Algoritmo de Fleury
O(m² )Construye un camino euleriano recorriendo el grafo y evitando cruzar un puente mientras haya otra arista disponible.
Grafos eulerianos
Algoritmo de Prim
O(m log n)Incluye vértices uno a uno: en cada paso añade la arista de menor peso entre V(T) y los vértices aún no seleccionados.
Árbol de expansión mínima
Algoritmo de Kruskal
O(m log m)Incluye aristas, no vértices: ordena las aristas por peso no decreciente y acepta cada una que no forme ciclo con las ya incluidas en E(T).
Árbol de expansión mínima
Algoritmo de Dijkstra
O(n²)"Cierra" un vértice por iteración, siempre el de menor dist, y relaja las aristas tensas que salen de él.
Caminos mínimos
Algoritmo de Bellman-Ford
O(n · m)Programación dinámica: examina todas las aristas en cada iteración, relajando las que estén tensas, durante |V(G)| − 1 iteraciones.
Caminos mínimos
Algoritmo de Floyd-Warshall
O(n³)Caminos mínimos entre todos los pares mediante programación dinámica: la ronda k habilita el vértice k como intermedio.
Caminos mínimos
Método de Ford-Fulkerson
O(m · f) con capacidades enterasMientras exista algún camino aumentante en G'(f), envía por él el cuello de botella δ y actualiza la red residual.
Flujo máximo
Algoritmo de Edmonds-Karp
O(n · m² )Implementación eficiente de Ford-Fulkerson: en cada iteración elige el camino aumentante más corto, obtenido mediante una búsqueda en anchura.
Flujo máximo
Algoritmo de Dinic
O(n² · m)En cada iteración construye la red de niveles GL a partir de G′(f) y determina en ella un flujo bloqueante.
Flujo máximo
Algoritmo de Kahn
O(n + m)En cada paso toma un vértice con grado de entrada cero, lo añade al final del resultado y reduce el grado de entrada de sus sucesores.
Ordenación topológica
Ordenación topológica por búsqueda en profundidad
O(n + m)Descrito por Tarjan en 1976: inserta cada vértice al principio del resultado solo después de visitar todos los que dependen de él.
Ordenación topológica
Algoritmo de Edmonds
O(n² · m)Busca caminos M-aumentantes entre vértices expuestos, contrayendo las flores (blossoms) que aparecen, hasta que no quede ninguno.
Emparejamiento
Coloración voraz
O(n + m)Recorre los vértices en cualquier orden y asigna a cada uno el color de menor índice que no use ninguno de sus vecinos.
Coloración
Algoritmo de Welsh-Powell
O(n² )Ordena los vértices por grado no creciente y colorea con un mismo color todos los que no estén conectados a un vértice ya coloreado con él.
Coloración