# Prim's Algorithm

This article needs to be linked to other articles.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{MissingLinks}}` from the code. |

## Algorithm

The purpose of this algorithm is to produce a minimum spanning tree for any given weighted graph $G$.

**Step 1**: Choose any vertex of $G$, and add it to $T$.

**Step 3**: If $T$ spans $G$,**stop**. Otherwise, go to**Step 2**.

## Proof

The above constitutes an algorithm, for the following reasons:

### Finiteness

For each iteration through the algorithm, **step 2** is executed, which increases the number of edges in $T$ by 1.

As a tree with $n$ nodes has $n - 1$ edges, the algorithm will terminate after $n - 1$ iterations.

### Definiteness

**Step 1**: Trivially definite.

**Step 2**: As the edges connecting $T$ to the remaining vertices can be arranged in order of weight, there is a definite edge (or set of edges) with minimal weight.

**Step 3**: It is straightforward to determine whether all the vertices are connected.

### Inputs

The input to this algorithm is the weighted graph $G$.

### Outputs

The output to this algorithm is the minimum spanning tree $T$.

### Effective

Each step of the algorithm is basic enough to be done exactly and in a finite length of time.

## Also known as

It is clear that **Prim's Algorithm** is a greedy algorithm: at each stage the minimum possible weight is chosen, without any analysis as to whether there may be a combination of larger weights which may produce a smaller-weight spanning tree.

For this reason, it is sometimes called **Prim's Greedy Algorithm**.

In this case, the greedy algorithm *does* produce the minimum spanning tree.

## Also see

## Source of Name

This entry was named for Robert Clay Prim.

## Historical Note

Prim's Algorithm was initially developed in $1930$ by Czech mathematician Vojtěch Jarník.

Robert Clay Prim independently discovered it in $1957$, and in $1959$ it was rediscovered once more by Edsger Wybe Dijkstra.

For these reasons it is also known as the **DJP Algorithm**, the **Jarník Algorithm**, or the **Prim-Jarník Algorithm**.

## Sources

- 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**Prim's algorithm** - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**tree** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**Prim's algorithm** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**tree** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**Prim's algorithm**