Prim's MST Algorithm

Greedy vertex-based Minimum Spanning Tree expansion.

Strategy

Vertex-Centric

Grow the tree one vertex at a time

Frontier

Lightest Edge

Choose minimum crossing edge

Priority Queue

Track best edges to neighbors

When to Use Prim's

Dense graphs with many edges (O(V^2) is competitive)
Finding a Minimum Spanning Tree in a single connected component
When building a network from a central starting point
Memory constraints are not an issue

Core Idea

Prim's algorithm starts with a single vertex and greedily expands the tree by adding the nearest vertex (smallest weight edge) connecting the existing tree to an outside vertex. This "nearest neighbor" property ensures we always make a safe choice for the MST.

Algorithm Metrics

Time

O(E log V)

Space

O(V)

Approach

Vertex-based

Best for

Dense graphs

Back: Kruskal Next: Topological Sort