logo
SEE ALGORITHMS

Kruskal's Algorithm Visualization

Kruskal's Algorithm is another way to find a Minimum Spanning Tree (MST) in a graph. It works by iteratively adding the cheapest available edge that connects two previously disconnected components, without forming a cycle. It is efficient for sparse graphs and uses a Union-Find data structure to detect cycles. Compare it with Prim’s Algorithm, which grows the MST from a single vertex, or Borůvka’s Algorithm which merges components in parallel.

Pseudocode

sort edges by weight (ascending)
MST = empty set
for each vertex v:
    create a disjoint set {v}
for each edge (u, v):
    if find(u) ≠ find(v):
        add (u, v) to MST
        union(u, v)

Step by Step

  • Sort all edges in non-decreasing order of their weights.
  • Initialize an empty set of edges for the MST.
  • Initialize a Disjoint set structure with each vertex in its own set.
  • For each edge (u, v) in the sorted list:
    • Use Find operation to determine the sets of u and v.
    • If the sets are different, the edge does not form a cycle. Add it to the MST.
    • Merge the two sets using Union operation.

Draw Graph
Union-Find

Common Interview Questions

What is the role of the Disjoint Set Union (DSU) in Kruskal's algorithm?

Kruskal's algorithm sorts all edges by weight and greedily considers them. DSU efficiently checks whether the endpoints of a candidate edge belong to the same connected component (find) to avoid forming cycles, and merges components (union).

Compare Prim's vs Kruskal's algorithm for sparse graphs vs dense graphs.

Kruskal's is faster for sparse graphs (E ≈ V) because edge sorting is quick. Prim's (especially with adjacency lists or Fibonacci heaps) performs better on dense graphs (E ≈ V²) where handling all V² edges in DSU is slower.

How do Path Compression and Union by Rank optimize the Disjoint Set Union (DSU) in Kruskal’s algorithm?

Union by Rank attaches the shallower tree under the deeper tree to keep tree height bounded by O(log V). Path Compression flattens the tree during find operations by pointing visited nodes directly to the root. Together, they reduce the amortized cost per DSU operation, making Kruskal's overall runtime dominated by edge sorting O(E log E).


💬  Discussion

to join the discussion


Curious to Learn More?

Hand-picked resources to deepen your understanding


Learn DSA on Udemy
Learn DSA on Udemy
As an Udemy Associate, I earn from qualifying purchases.

© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0