Kruskal's Algorithm

A greedy algorithm that finds a minimum spanning tree by sorting edges and adding them one by one while avoiding cycles, typically using Union-Find.

Kruskal's Algorithm Visualization

How to use: Click empty space to add a vertex. Click two vertices to add an undirected weighted edge. Drag to reposition. Right-click to delete.

Speed: 5x

SlowFast

🔊 Sound

Ready

● Considering● Added to MST● Rejected (cycle)● In MST

Edges (sorted by weight)

Union-Find Components

—

MST Edges

—

Complexity

Time Complexity: O(E log E)

Space Complexity: O(V)

Pseudocode

function kruskal(graph):
  sort edges by weight
  uf = UnionFind()
  mst = []
  for edge in edges:
    u, v = edge endpoints
    if find(u) != find(v):
      union(u, v)
      add edge to mst
  return mst