Prim's Algorithm Visualizer

Visualize how Prim's algorithm builds a minimum spanning tree by greedily adding the cheapest edge. Draw a weighted graph and watch the tree grow from a starting node.

Visualize Prim's Algorithm

How It Works

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a weighted undirected graph. It builds the tree by starting from an arbitrary node and repeatedly adding the cheapest edge that connects a tree node to a non-tree node.

The algorithm was developed by Vojtěch Jarník in 1930 and later independently rediscovered by Robert C. Prim in 1957. It guarantees the minimum total edge weight needed to connect all nodes.

  1. 1

    Start with an arbitrary node and add it to the MST

  2. 2

    Add all edges from the MST to a priority queue

  3. 3

    Extract the minimum-weight edge from the queue

  4. 4

    If the edge connects to a node not yet in the MST, add that node and edge

  5. 5

    Add all edges from the newly added node to the priority queue

  6. 6

    Repeat until all nodes are in the MST or the queue is empty

Key Properties

Time Complexity

O((V + E) log V) with a binary heap, or O(E + V log V) with a Fibonacci heap.

Minimum Weight

Produces a spanning tree with the minimum possible total edge weight.

Greedy Approach

Always picks the cheapest available edge, building the MST incrementally from a single starting node.

Connected Graphs

Works on connected weighted undirected graphs. For disconnected graphs, it produces a minimum spanning forest.

Common Use Cases

  • Network design — minimizing cable length to connect all offices in a building
  • Cluster analysis — building hierarchical clusters by connecting nearest data points
  • Circuit design — minimizing wire length on printed circuit boards

Frequently Asked Questions

What is a minimum spanning tree?
A minimum spanning tree (MST) is a subset of edges in a connected, weighted, undirected graph that connects all vertices with the minimum possible total edge weight, without forming any cycles.
What is the difference between Prim's and Kruskal's algorithm?
Both find minimum spanning trees, but they work differently. Prim's grows the MST from a single starting node by adding the cheapest adjacent edge. Kruskal's sorts all edges by weight and adds them one by one, skipping edges that would create a cycle.
Does Prim's algorithm work on directed graphs?
No. Prim's algorithm is designed for undirected graphs only. For directed graphs, finding a minimum spanning arborescence requires different algorithms like Edmonds' algorithm.
What is the time complexity of Prim's algorithm?
With a binary heap, Prim's algorithm runs in O((V + E) log V) time. With a Fibonacci heap, this improves to O(E + V log V), which is faster for dense graphs.

Ready to see it in action?

Open the Visualizer