Minimum Spanning TreeLesson 40Free preview

DSA Kruskal's

This lesson is part of DSA · All levels

Summary

The Kruskal's algorithm sort all sides by weight, then insert sides one by one as long as they don't form a cycle. The union-find data structure is used to check whether two nodes are already in the same component. This algorithm works well on rare graphs with complexity.

Key points

Sort the sides from the smallest weight, then connect the valid ones
Union-find detects the side that will form the cycle
Stop after the V-1 side selects
Complexity, suitable for rare graphs

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.