Explain Prim's Algorithm.

Difficulty: 5/10

minimum spanning tree, priority queue, graph representation

Prim's Algorithm

Prim's algorithm grows an MST from a starting vertex. At each step, it selects the minimum-weight edge connecting the already-built tree to an unvisited vertex. A priority queue efficiently maintains candidate edges or vertex keys.

javascript

1
Starts from an arbitrary vertex.
2
Grows one connected MST.
3
Priority queue is commonly used.
4
With binary heap and adjacency list: O(E log V).
5
Suitable for dense graphs with appropriate implementations as well.

Scenario Questions

0-2 years experience

Follow-up Questions