Cómo ejecutar Prim o Kruskal 01 Construye un grafo ponderado. Prueba el preajuste Cuadrícula (rows 4, cols 5 — 20 nodos, 31 aristas unitarias), un grafo Random conectado o Complete K₆. 02 Elige Prim y fija Source , o cambia a Kruskal, que no necesita fuente. 03 Lee la tabla. Primero el peso total, luego aristas elegidas, componentes y es-bosque; debajo está una fila por arista elegida con su peso. 04 Cruza el resultado con el otro algoritmo — ambos deben coincidir en el peso total para el mismo grafo. 05 Avanza la ejecución con Play / Prev / Next; Prim resalta la frontera creciente, Kruskal las aristas aceptadas y rechazadas.
Ejemplos resueltos Valores tal como los muestra el panel:
Grafo · algoritmo
Lectura
Cuadrícula 4 × 5, Prim desde 1-1
peso total 19 ; aristas elegidas 19 / 31 ; componentes 1 ; es bosque No
Cuadrícula 4 × 5, Kruskal
peso total 19 ; aristas elegidas 19 / 31
Random conectado (n 6, p 0.3, seed 20260730, peso máx. 9), Prim desde A
peso total 16 ; elegidas A–B(3), A–C(4), C–E(2), A–D(6), D–F(1) ; aristas elegidas 5 / 7
El mismo grafo, Kruskal
peso total 16 ; las mismas cinco aristas en orden de peso: D–F(1), C–E(2), A–B(3), A–C(4), A–D(6)
Complete K₆, Prim
peso total 5 ; aristas elegidas 5 / 15 ; aristas A–B(1), A–F(1), A–E(1), A–D(1), A–C(1)
El MST de la cuadrícula son 19 aristas unitarias para 20 nodos —el mínimo teórico— y ambos algoritmos lo alcanzan. En el grafo aleatorio basta una arista para comprobar la respuesta a mano: D–F pesa 1 , la más ligera del grafo, así que todo MST debe contenerla, y ambas ejecuciones lo hacen.
Por qué difieren las dos listas Prim y Kruskal eligen aristas en órdenes distintos y, en empates, pueden elegir árboles válidos diferentes. Kruskal ordena todas las aristas globalmente, así que su tabla empieza por la arista más ligera en cualquier parte; Prim solo mira la frontera de un árbol que crece, así que su tabla empieza por lo que sale primero de la raíz. En el grafo aleatorio ambos producen el mismo conjunto —el árbol de expansión mínimo allí es único—, pero la lista de K₆ (todos los pesos 1) es solo uno de muchos árboles perfectos: compara peso total y número de aristas, no listas de aristas, cuando los pesos se repiten.
Límites
Un grafo desconectado da un bosque. La fila es-bosque pasa a Sí y el número de componentes se mantiene por encima de 1; la respuesta es entonces un bosque de expansión mínimo, un árbol por componente, no un solo árbol.
Solo aristas no dirigidas. Prim trata un grafo dirigido como no dirigido y lo advierte; la fusión de componentes de Kruskal también es una idea no dirigida. Ninguno de los dos resuelve la arborescencia mínima dirigida.
La trampa del desempate En Complete K₆ cada arista pesa 1 , así que cada árbol de expansión pesa 5 ; Prim responde casualmente con una estrella alrededor de A: A–B, A–F, A–E, A–D, A–C . Lee esa lista como un árbol mínimo, no como el árbol mínimo. La misma cautela se aplica a las cuadrículas de pesos iguales: la respuesta de la cuadrícula 19 es estable, pero cuáles 19 aristas unitarias aparecen puede diferir entre Prim y Kruskal mientras ambos siguen siendo correctos.
Dónde es útil Comprobar una propuesta de cableado más barato En el grafo aleatorio, las dos aristas más pesadas, E–F(8) y B–D(7) , quedan ambas excluidas mientras A–D(6) se acepta. Comprueba una red propuesta del mismo modo: si paga E–F(8) y deja fuera la más barata D–F(1), no es mínima.
Enseñar la propiedad del corte La cuadrícula hace visible el razonamiento de cortes: cada arista unitaria cruza algún corte con peso 1, y ambos algoritmos aceptan 19 de las 31 sin un solo ciclo. Cambia al grafo Random conectado y ejecuta ambos; la reproducción por pasos muestra a Kruskal saltándose E–F(8) porque sus extremos ya están unidos.
Privacidad La edición del grafo y ambas ejecuciones MST se ejecutan localmente en tu navegador; nada se sube.
Referencias
Wikipedia, Prim's algorithm , en.wikipedia.org (访问日期:2026-10-07)— crecimiento de la frontera desde una raíz.
Wikipedia, Kruskal's algorithm , en.wikipedia.org (访问日期:2026-10-07)— orden por peso con union-find.
Wikipedia, Minimum spanning tree , en.wikipedia.org (访问日期:2026-10-07)— propiedades de corte y ciclo, unicidad con pesos distintos.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4.ª ed., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— algoritmos MST y la propiedad del corte.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07