logo
SEE ALGORITHMS

Prim's Algorithm Visualization

Prim's Algorithm builds a Minimum Spanning Tree (MST) by starting with a single node and "growing" the tree outward. At every step, it finds the cheapest edge that connects a node inside the growing tree to a node outside of it. This greedy approach continues until all nodes are part of the tree, ensuring the total weight of all edges is as low as possible. It is perfect for problems like designing cost-effective road, fiber-optic, or electrical utility networks.

Pseudocode

MST = empty set
mark src as visited
while MST does not span all vertices:
    (u, v) = cheapest edge where
             u ∈ visited and v ∉ visited
    add edge (u, v) to MST
    mark v as visited

Step by Step

  1. Initialize an empty set of edges for the MST.
  2. Start with an arbitrary vertex and mark it as visited (part of MST).
  3. Find the cheapest edge connecting a vertex in the MST to a vertex outside the MST.
  4. Add this edge to the MST and mark the new vertex as visited.
  5. Repeat until all vertices are part of the MST.

Draw Graph

AI Summary

(5 credits)

See what happens with your input

Get a short, step-by-step explanation of this visualization. Turn on AI Summary, then start a fresh run with your input.


How It Works

Prim's algorithm maintains two disjoint sets of vertices: those already included in the growing Minimum Spanning Tree, and those not yet added. Starting from a chosen root vertex, the algorithm continually examines all edges spanning the boundary between the tree and the remaining vertices. The minimum-weight edge crossing this cut is guaranteed to belong to the MST.

In practical implementations, a priority queue tracks the minimum known distance from the MST to each outside vertex. Whenever a new vertex is absorbed into the tree, the distances to its adjacent unvisited neighbors are updated via decrease-key operations.

When to Use

Prim's algorithm is particularly effective for dense graphs where the number of edges E approaches V². While a standard binary heap yields O(E log V) runtime, implementing Prim's with a Fibonacci heap reduces the amortized cost of decrease-key operations to strictly O(1). This brings Prim's overall runtime down to O(E + V log V), which is asymptotically optimal and significantly outperforms Kruskal's algorithm on dense networks.

Time & Space Complexity

Metric / Operation
Complexity
Description
With Binary HeapO(E log V)Extract-min and decrease-key operations on a binary heap take O(log V) across all edges and vertices.
With Fibonacci HeapO(E + V log V)Fibonacci heap achieves O(1) amortized decrease-key operations, making Prim’s asymptotically optimal for dense graphs.
Adjacency MatrixO(V²)Simple linear array scan for minimum edge; optimal for extremely dense graphs where E ≈ V².
Space ComplexityO(V + E)Stores graph adjacency structure and priority queue entries for all vertices.

Common Interview Questions

What fundamental greedy choice property guarantees the correctness of Prim's algorithm?

The Cut Property: For any cut (partition of vertices into two sets S and V - S), the minimum weight edge crossing the cut must belong to the Minimum Spanning Tree (MST). Prim's iteratively grows a single tree set S by adding the lightest crossing edge.

Compare Prim's algorithm performance using Adjacency List + Min-Heap vs Fibonacci Heap.

Binary Min-Heap implementation yields O((V + E) log V). A Fibonacci Heap optimizes decreaseKey operations to amortized O(1), improving overall time complexity to O(E + V log V), which is superior for dense graphs where E ≈ V².

How does Prim's algorithm behave if the graph contains negative edge weights or disconnected components?

Prim's algorithm works correctly with negative edge weights. However, if the graph is disconnected, Prim's will only build an MST for the connected component containing the starting node. To span all components, Prim's must be launched on each unvisited component (Minimum Spanning Forest).

Where is Prim's algorithm applied in network infrastructure engineering?

Designing physical fiber-optic cables, electrical power grids, water supply pipe connections, and telecommunication layout networks to minimize physical infrastructure construction costs.


💬  Discussion

to join the discussion


Curious to Learn More?

Hand-picked resources to deepen your understanding


Learn DSA on Udemy
Learn DSA on Udemy
As an Udemy Associate, I earn from qualifying purchases.

© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0