Prim’s Algorithm For Minimum Spanning Tree (Mst) :What You Need To Know

What is Prim’s Algorithm for Minimum Spanning Trees?

Prim’s algorithm is a computer science algorithm used to find a minimum spanning tree from a weighted-edge graph. It’s a greedy algorithm, much like Krsukal’s algorithm. A greedy algorithm follows the most optimal technique for finding a solution on a step-by-step rather than a global scale. Greedy algorithms can be excellent for approximating a globally optimal solution to a problem but may be slower in general than more optimal, non-greedy algorithms.

Prim’s algorithm is used to find minimum spanning trees. Minimum spanning trees are a type of graph in which all vertices are connected without creating any cycles, and the overall weight of the edges of the graph is at the lowest it can possibly be.

Prim’s algorithm was actually first discovered by Czech mathematician Vojtěch Jarník in 1930 and rediscovered and published by computer scientists Robert C. Prim and Edsger W. Dijkstra in 1957 and 1959, respectively. As such, the algorithm is sometimes called Jarnik’s algorithm, the Prim–Jarník algorithm, the Prim–Dijkstra algorithm, or the DJP algorithm.

How Does Prim’s Algorithm Work?

Prim’s algorithm has six steps on paper, although several steps are repeated indefinitely until the program can logically reach the next step. However, when coding the program requires many more than the six basic steps required to complete the algorithm on paper.

The six steps on paper are as follows:

1. Determine an arbitrary vertex as the starting point of the minimum spanning tree.
2. Find the edges with the lowest weights connecting to the starting point of the minimum spanning tree.
3. Continue connecting vertices using the edges with the lowest weights without creating cycles.
4. Once there exist fringe vertices that are not connected to the graph, begin finding the edges with the lowest weights that connect the fringe vertices to the minimum spanning tree.
5. Add the edges that do not create cycles until all vertices are connected.
6. Complete the minimum spanning tree.

Is Prim’s Algorithm Correct? What’s the Proof for Prim’s Algorithm?

Prim’s algorithm has been proven correct and published on multiple occasions since being discovered by Jarnik in 1930. There are many published proofs you can read for Prim’s algorithm. However, we’ll be using the one from Hein’s Discrete Structures.

Theorem 1 If S is the spanning tree selected by Prim’s algorithm for input graph G = (V, E),

then S is a minimum-weight spanning tree for G.

Proof: The proof is by contradiction, so assume that S is not minimum weight. Let ES =

(e1, e2, · · · , en−1) be the sequence of edges chosen (in this order) by Prim’s algorithm, and let

U be a minimum-weight spanning tree that contains edges from the longest possible prefix of

sequence ES.

Let ei = {x, y} be the first edge added to S by Prim’s algorithm that is not in U, and let

W be the set of vertices immediately before {x, y} is selected. Notice that it follows that U

contains edges e1, e2, · · · , ei−1 but not edge ei

There must be a path x ❀ y in U, so let {a, b} be the first edge on this path with one

endpoint (a) inside W, and the other endpoint (b) outside W, as in the following picture:

Define the set of edges T = U + {{x, y}} − {{a, b}}, and notice that T is a spanning tree for

graph G. Consider the three possible cases for the weights of edges {x, y} and {a, b}:

Case 1, w({a, b}) > w({x, y}): In this case, in creating T we have added an edge that has

smaller weight than the one we removed, and so w(T) < w(U). However, this is impossible, since U is a minimum-weight spanning tree.

Case 2, w({a, b}) = w({x, y}): In this case w(T) = w(U), so T is also a minimum spanning

tree. Furthermore, since Prim’s algorithm hasn’t selected edge {a, b} yet, that edge

cannot be one of e1, e2, · · · , ei−1. This implies that T contains edges e1, e2, · · · , ei

, which

is a longer prefix of ES than U contains. This contradicts the definition of tree U.

Case 3, w({a, b}) < w({x, y}): In this case, since the weight of edge {a, b} is smaller, Prim’s

algorithm will select {a, b} at this step. This contradicts the definition of edge {x, y}.

Since all possible cases lead to contradictions, our original assumption (that S is not minimumweight) must be invalid. This proves the theorem.

Prim’s algorithm can be further expressed using the following pseudocode:

T = ∅;
U = { 1 };
while (U ≠ V)
    let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U;
    T = T ∪ {(u, v)}
    U = U ∪ {v}

Practical Applications of Prim’s Algorithm

Prim’s algorithm and its sister algorithm, Kruskal’s algorithm, are useful in life, not just in higher mathematics and computer programming. If you’ve ever used Google maps, you’ve used the types of graphs used in Prim’s and Kruskal’s algorithms. Whether the graph is densely populated or typically populated will determine which algorithm will perform better. Kruskal’s algorithm performs better with typical graphs and will struggle and even produce suboptimal results when used on a dense graph. However, if you use Kruskal’s algorithm on a dense graph, you can check the results by running the resulting graph through a program running Prim’s algorithm.

The following real-life use cases often use Kruskal’s algorithm:

• TV Networking
• LAN Networking
• Networking pipes for water or gas
• Electrical grids
• Single-link clusters
• Tour operations
• Landing cables

The following real-life uses cases may need to be further checked with Prim’s algorithm:

• Any use case where you would use Kruskal’s algorithm can be resolved using Prim’s algorithm
• Game Development
• Irrigation channels 
• Placing microwave towers
• Traveling Salesman Problem
• Designing a fiber-optic grid or ICs
• Cluster analysis
• Pathfinding algorithms used in AI (Artificial Intelligence)
• Cognitive Science
• Network for roads and Rail tracks connecting all the cities

Practical Examples of Prim’s Algorithm in Code

If you actually want to use Prim’s algorithm, you’ll need to be able to code a computer to use it effectively as doing the math for the algorithm manually is unrealistic unless the graph is rather small. You can create a program that performs Prim’s algorithm on a graph in pretty much any coding language, but we’ll include usable programs for a few different languages.

Python

INF = 9999999
V = 5
G = [[0, 9, 75, 0, 0],
     [9, 0, 95, 19, 42],
     [75, 95, 0, 51, 66],
     [0, 19, 51, 0, 31],
     [0, 42, 66, 31, 0]]
selected = [0, 0, 0, 0, 0]
no_edge = 0
selected[0] = True
print("Edge : Weight\n")
while (no_edge < V - 1):
     minimum = INF
    x = 0
    y = 0
    for i in range(V):
        if selected[i]:
            for j in range(V):
                if ((not selected[j]) and G[i][j]):  
                    # not in selected and there is an edge
                    if minimum > G[i][j]:
                        minimum = G[i][j]
                        x = i
                        y = j
    print(str(x) + "-" + str(y) + ":" + str(G[x][y]))
    selected[y] = True
    no_edge += 1

Java

import java.util.Arrays;
class PGraph {
  public void Prim(int G[][], int V) {
    int INF = 9999999;
    int no_edge; // number of edge
    boolean[] selected = new boolean[V];
    Arrays.fill(selected, false);
    no_edge = 0;
    selected[0] = true;
    System.out.println("Edge : Weight");
    while (no_edge < V - 1) {
      int min = INF;
      int x = 0; // row number
      int y = 0; // col number
      for (int i = 0; i < V; i++) {
        if (selected[i] == true) {
          for (int j = 0; j < V; j++) {
            if (!selected[j] && G[i][j] != 0) {
              if (min > G[i][j]) {
                min = G[i][j];
                x = i;
                y = j;
              }
            }
          }
        }
      }
      System.out.println(x + " - " + y + " :  " + G[x][y]);
      selected[y] = true;
      no_edge++;
    }
  }
  public static void main(String[] args) {
    PGraph g = new PGraph();
    int V = 5;
    int[][] G = { { 0, 9, 75, 0, 0 }, { 9, 0, 95, 19, 42 }, { 75, 95, 0, 51, 66 }, { 0, 19, 51, 0, 31 },
        { 0, 42, 66, 31, 0 } };
    g.Prim(G, V);
  }
}

Final Thoughts

Prim’s algorithm is just one type of higher mathematics used daily to perform functions for the technology and infrastructure in our world. While the average person will likely never see a use for Prim’s algorithm, it never hurts to learn more about higher mathematics. If you enjoyed learning a little bit about this algorithm and how it works, leave us a comment here or on social media!

The image featured at the top of this post is ©Pixel-Shot/Shutterstock.com.