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.
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.
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0