Explain Kruskal's Algorithm. Which data structure is crucial for it?

Difficulty: 5/10

minimum spanning tree, union‑find, graph algorithms

Kruskal's Algorithm

Kruskal's algorithm constructs an MST by sorting all edges by weight and repeatedly adding the smallest edge that does not create a cycle. Union-Find, also called Disjoint Set Union, efficiently determines whether two vertices are already connected and merges components when an edge is accepted.

javascript

1
Sort edges by ascending weight.
2
Use Union-Find for cycle prevention.
3
Typical complexity: O(E log E).
4
Works naturally with edge-list representations.
5
For a connected graph, the result contains V-1 edges.

Scenario Questions

0-2 years experience

Follow-up Questions