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.
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.
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.