Prim's algorithm is used to find the minimum spanning tree of a graph. In this article, we'll introduce the algorithm and the core concepts, discuss its complexity, then show full code implementations in multiple languages.
Prim's Algorithm
Prim's algorithm, also known as Jarník's algorithm, is an algorithm that finds a minimum spanning tree for a weighted and undirected graph. This means the graph can have weighted edges, but must either not have directed edges, or the edges must be the same in both directions. A spanning tree is a tree which touches all vertices in a graph but only has a subset of the edges of that graph: a set of edges which connects all of the vertices with the smallest possible sum weight. Finding minimum spanning trees is useful in certain real-life applications which involve finding cost-effective ways to connect objects together.
Description of Algorithm
This algorithm is similar to depth-first search and breadth-first search algorithms. The steps can be summarized as:
- Create a new graph spanning tree which will hold our solution.
- Create a priority queue to hold edges. This queue which will return lowest cost edges first.
- Create a set to record nodes which have already been visited.
- Pick a start vertex, add all of its outgoing edges to the queue, and mark it as visited.
- While the queue is not empty:
- Take an edge from the queue, and if the "right side" vertex has not been visited, proceed with the remaining steps.
- Add this edge to the spanning tree.
- Add both of its vertices to the spanning tree.
- Add all of its outgoing edges to the queue.
This algorithm is a greedy algorithm because it always adds edges with lower weights first. The full code implementation is included in the last section of this article.
Space and Time Complexity
In the table below, e represents the number of edges and v represents the number of vertices.
Complexity | Notes | |
---|---|---|
Space | O(e + v) | We allocate linear extra space for the priority queue and visited nodes set. |
Time | O(e log v) | The priority queue reduces the time of finding minimum weights from O(n) to O(log n), thus, we have log v. |
Full Implementation
The full implementation is included below. In some languages, the code also includes additional classes for certain data structures: