Minimum Spanning TreeLesson 39Free preview

DSA Prim's

This lesson is part of DSA · All levels

Summary

Prim builds the MST by growing from an initial node: each step adds a side with the smallest weight that connects the tree to the node outside it. With priority queue, the complexity is O(E log V) and it is very efficient for solid graphs. The process continues until all nodes are included.

Key points

Growing from one node, adding the cheapest side to the new node
Using the priority queue to select the cheapest side
Complexity with heap
Suitable for a solid graph with many sides

Full lesson

Code examples and quizzes

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