Árbol de expansión mínimo
Encontrar conexiones económicas con Kruskal y examinar las decisiones de unión y búsqueda.
Acerca de esta herramienta
Conectar nodos sin ciclos con el mínimo peso total. Una arista no dirigida por línea: A B 4. A solo añade un nodo aislado. Se ignoran líneas vacías o que empiezan por #. Identificadores: 1–24 letras ASCII, dígitos, puntos, guiones o guiones bajos. Pesos con punto decimal y exponente opcional; se admite cero y valores negativos. Límites: 24 nodos, 80 aristas distintas, 12.000 caracteres, pesos entre −1e9 y 1e9. A B 4 y B A 4 cuentan una vez; distintos pesos conservan aristas paralelas.
Calcular entrega el resultado inmediatamente; Paso examina una arista. Animación opcional de 0–2000 ms, inicialmente 350. Pausa/Continuar conserva el recorrido; Calcular puede terminarlo. Restablecer o editar descarta el recorrido. Los borradores del grafo y de la espera se guardan localmente, incluso incompletos o no válidos. Recargar restaura las entradas sin calcular; no se guarda el progreso.
Kruskal examina pesos crecientes. Unión y búsqueda acepta una arista solo entre componentes distintos; de lo contrario crearía un ciclo. Unión por rango y división de caminos aceleran las búsquedas. Los empates usan identificadores ordenados sensibles a mayúsculas. Puede haber otros árboles mínimos válidos. Ordenación O(E log E), operaciones amortizadas casi constantes. Se examinan todas las aristas para mostrar ciclos rechazados, incluso después de formar el árbol.
La red inicial pesa 13: B–C 1, B–D 2, E–F 2, A–C 3, C–E 5. Entradas desconectadas producen un árbol mínimo por componente, incluidos nodos aislados: un bosque de expansión mínimo. No calcula caminos más cortos ni rutas de viaje. Siempre rechaza bucles. La longitud geométrica no representa el peso.
Seis colores ayudan a distinguir componentes y se repiten si hay más; los miembros exactos figuran en la tabla. Aristas elegidas verdes, rechazadas rojas discontinuas, arista actual más gruesa. Tablas muestran aristas elegidas, miembros y decisiones examinadas. Identificadores largos usan números en el grafo; más de 16 nodos permiten desplazamiento local. Aristas densas pueden solaparse. Aritmética de coma flotante; hasta 12 cifras significativas mostradas.