Saltar al contenido principal
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

Graph Algorithms Visualizer

Kruskal's MST

Time O(E log E) · Space O(V)
Paso 0 / 0
Speed 100ms
Step Progress 0 / 0
Visited 0
Frontier 0
Status Ready
Unvisited
Start
Active
Visited
MST / SPT
Rejected
SCC component

Queue

Step Explanation

Select an algorithm and press Play to begin.

Pseudocode 
 
 
 
 
  
 
 
Kruskal's Minimum Spanning Tree
  
 
  Intermediate (3/5)
 
~1 hora   Minimum Spanning Tree (MST)  Union-Find / DSU  Ordenamiento de aristas  Cycle detection  
Prereqs: Grafos ponderados, Ordenamiento  
 
Quick Reference
Kruskal's Algorithm
Kruskal's algorithm finds a Minimum Spanning Tree (MST) by sorting all edges by weight and adding the cheapest edge that does not form a cycle, using the Union-Find data structure.

Difficulty: Intermediate (3/5)
graph
Complexity
Best Time
O(E log E)
Average Time
O(E log E)
Worst Time
O(E log E)
Space
O(V)
When to Use
Use Kruskal's for sparse graphs, or when edges can be easily sorted. Often preferred for its simplicity and the fact that it only needs an edge list.
Pros
  • Simple edge-sorting approach
  • Performs well on sparse graphs
  • Uses Union-Find for near-linear cycle detection
Cons
  • Requires sorting all edges (E log E)
  • Must check for cycles on every edge
  • Not as efficient as Prim on dense graphs
History
Kruskal's algorithm was published by Joseph Bernard Kruskal Jr. in 1956 in the Proceedings of the American Mathematical Society.
 
 
Kruskal’s algorithm construye un Minimum Spanning Tree (MST) ordenando todas las aristas por peso y añadiéndolas en orden creciente, siempre que no formen un ciclo. Es simple, elegante, y usa Union-Find para detectar ciclos en casi-constante tiempo.


A diferencia de Prim (que crece un árbol), Kruskal trata todas las aristas por igual: las más baratas ganan. Si una arista conecta dos componentes diferentes, es segura; si ya están conectados, la arista crearía un ciclo y se descarta.


Cómo Funciona


    

  1. Ordena todas las aristas por peso ascendente.
    2. 

  2. Inicializa DSU con cada nodo como su propio componente.
    3. 

  3. Escanea las aristas ordenadas:

      

    • “Si find(u) != find(v): añade la arista al MST, une los componentes.”
      • 

    • “Si find(u) == find(v): descarta (ciclo).”
      • 

    

    4. 

  4. Detiene cuando el MST tiene V-1 aristas.
    5. 



Idea Clave


Ordenar aristas es la clave: al considerar las más baratas primero, garantizas que cada arista añadida es la más barata posible para conectar sus dos componentes. Eso es exactamente la cut property, pero aplicada implícitamente por el orden global.


Union-Find con path compression y union by rank hace que find() y union() sean O(α(n)) (casi constante), por lo que el bottleneck es el sort: O(E log E).


Ejemplo Trabajado


Grafo con aristas:


A-B(2), A-D(4), B-C(3), B-D(1), C-D(5), D-E(2)


Ordenadas: (B-D,1), (D-E,2), (A-B,2), (B-C,3), (A-D,4), (C-D,5)


DSU inicial: {A},{B},{C},{D},{E}


    

  1. B-D(1): find(B)≠find(D) → MST += {B-D}. Union: {A},{B-D},{C},{E}
    2. 

  2. D-E(2): find(D)≠find(E) → MST += {D-E}. Union: {A},{B-D-E},{C}
    3. 

  3. A-B(2): find(A)≠find(B) → MST += {A-B}. Union: {A-B-D-E},{C}
    4. 

  4. B-C(3): find(B)≠find(C) → MST += {B-C}. Union: {A-B-C-D-E}
    5. 

  5. A-D(4): find(A)==find(D) → descartada (ciclo)
    6. 

  6. C-D(5): find(C)==find(D) → descartada (ciclo)
    7. 



MST: {B-D, D-E, A-B, B-C} con peso total 1+2+2+3 = 8.


Casos Extremos y Trampas


    

  • Grafo disperso — O(E log E) domina; DSU es casi gratis.
    • 

  • Grafo denso — E = V², O(V² log V²) = O(V² log V).
    • 

  • Empates en peso — cualquier orden entre aristas iguales funciona; todas producen MST válidos.
    • 

  • Grafo no conexo — Kruskal produce un Minimum Spanning Forest (un MST por componente).
    • 



Comparación con Prim





































AspectoKruskalPrim
DatosEdge listAdjacency list / matrix
Cycle detectionDSUImplicit (tree property)
DensoO(V² log V)O(V²) mejor
DispersoO(E log E) ≈ O(E log V)O(E log V)
Natural paraEdge-centric, dispersoVertex-centric, denso


Aplicaciones


    

  • Redes de computadoras — diseño de redes con costo mínimo
    • 

  • Layout de circuitos — minimizar longitud total de cables
    • 

  • Clusterización jerárquica — single-linkage clustering
    • 

  • Enseñanza — introduce DSU y greedy en grafos
    • 



Trayectoria de Práctica


    

  1. Ejecuta Kruskal en el visualizador; registra el orden de aristas y las uniones DSU.
    2. 

  2. Implementa DSU con path compression y union by rank; prueba en un grafo de 10 nodos.
    3. 

  3. ¿Por qué Kruskal funciona en grafos no conexos? ¿Qué retorna?
    4. 

  4. Compara con Prim en un grafo denso (V=50, E=1000).
    5. 

  5. Investiga Borůvka: ¿cómo elimina el sort de aristas?
    6.