Kruskal's Algorithm
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.
Step by Step
- Sort all edges in non-decreasing order of their weights.
- 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.
- Repeat until the MST contains V-1 edges.
Things to Observe
- Component Merging: Observe how adding an edge merges two previously separate components into one. The visualization shows nodes moving together as components are unified, demonstrating how the algorithm gradually connects all vertices.
- Cycle Detection: Watch how union-find data structure efficiently checks if two vertices are not in the same connected component before adding an edge.
Union-Find
Curious to Learn More?
Hand-picked resources to deepen your understanding
As an Amazon Associate, I earn from qualifying purchases. This helps support the site at no extra cost to you.
© 2025 SEE Algorithms. Code licensed under MIT, content under CC BY-NC 4.0.