Prim’s algorithm

Prim’s algorithm builds a minimum spanning tree (MST) of a connected, weighted graph by starting at an arbitrary vertex and repeatedly adding the cheapest edge that reaches a vertex not yet in the tree. A minimum spanning tree is a subset of edges that joins every vertex into one connected structure, without any cycle, at the lowest possible total weight.

Vojtěch Jarník first described the method in 1930, Robert C. Prim rediscovered it independently in 1957, and Edsger Dijkstra published it again in 1959. Those three separate discoveries left the algorithm with several names: Jarník’s algorithm, the Prim-Jarník algorithm, and the DJP algorithm, after Dijkstra, Jarník, and Prim.

The algorithm is greedy, which means it takes the cheapest option in front of it at each step and never goes back to reconsider. It keeps a set of vertices already in the tree and, at each step, examines the edges that cross from that set to the vertices still outside it. It then adds the lightest such crossing edge, along with the new vertex it reaches, and repeats until the tree spans every vertex.

Step through the build below to watch the tree grow one crossing edge at a time, and switch the starting vertex to confirm that every choice reaches the same minimum spanning tree. This particular graph has only one. When two edges tie in weight, a graph can have several spanning trees that share the same lowest total, and then the starting vertex decides which one you get.

Interactive diagram — enable JavaScript to view.

Prim’s algorithm resembles Dijkstra’s algorithm, as both grow a tree by greedily pulling in the nearest vertex through a priority queue. The difference is what each one minimizes: Prim weighs a single connecting edge, while Dijkstra weighs the total distance to a source. Kruskal’s algorithm is the other classic solution to the minimum spanning tree problem, and it reaches the same result by joining edges in weight order.

Performance depends on the data structure used to find the next cheapest crossing edge, usually stated in Big O notation over V vertices and E edges:

  • Adjacency matrix with linear search: Scanning every candidate on each step gives O(V^2) time, which suits dense graphs.
  • Binary heap and adjacency list: A min-heap used as a priority queue brings a sparse graph down to O(E log V).
  • Fibonacci heap and adjacency list: A more advanced priority queue lowers the theoretical bound to O(E + V log V).

Minimum spanning trees answer network-design questions, such as connecting a set of locations with cable, pipe, or road at the least total cost. Beyond that, Prim’s algorithm turns up in cluster analysis and in the random generation of mazes.

Build a Maze Solver in Python Using Graphs

Tutorial

Build a Maze Solver in Python Using Graphs

In this step-by-step project, you'll build a maze solver in Python using graph algorithms from the NetworkX library. Along the way, you'll design a binary file format for the maze, represent it in an object-oriented way, and visualize the solution using scalable vector graphics (SVG).

intermediate projects

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated July 30, 2026
Computer Science Glossary Share Feedback