*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: