Prims Algorithm- Explained with example!

Earlier in our articles, we briefly discussed the Dijkstra’s Algorithm and implement Dijkstra’s algorithm using Java program. In this article, we discuss the prims algorithm, its practical applications and finally, we implement that algorithm using Java.

WHAT IS PRIMS ALGORITHM?

It is an algorithm which is used to find the minimum spanning tree of the undirected graph. It uses the greedy technique to find the minimum spanning tree (MST) of the undirected graph. The greedy technique is the technique in which we need to select the local optimal solution with hope to find the global optimal solution.  Like every algorithm, prims algorithm has many practical applications  like:

• Many routing algorithms use this prims algorithm.
• If we need to minimize any electricity loss we can implement this algorithm and minimize the total cost of the wiring.
• You can find the minimum distance to transmit a packet from one node to another in large networks.
• It is used widely in topology and study of molecular bonds in chemistry.

ALGORITHM:

1:  Get the number of vertices (n) and weight of the edges from the user.

2: Consider any vertex in graph process the vertex and add the vertex to the tree.

3: Find the smallest edge from the graph connecting the edge of the vertex in the tree such that it does not form a cycle.

4: Add the vertex to the tree.

5: Repeat from step 4, until tree contains all the n vertices.

Let us see how to implement this algorithm in Java programming. If you need to implement this algorithm in any other programming languages let us know in the comment section.

PRIMS ALGORITHM USING JAVA :

import java.util.*;
import java.lang.*;
import java.io.*;
 
class prims
{
    private static final int V=5;
    int minKey(int key[], Boolean mstSet[])
    {
        int min = Integer.MAX_VALUE, min_index=-1;
 
        for (int v = 0; v < V; v++)
            if (mstSet[v] == false && key[v] < min)
            {
                min = key[v];
                min_index = v;
            }
 
        return min_index;
    }
    void printMST(int parent[], int n, int graph[][])
    {
        System.out.println("Edge   Weight");
        for (int i = 1; i < V; i++)
            System.out.println(parent[i]+" - "+ i+"    "+
                               graph[i][parent[i]]);
    }
    void primMST(int graph[][])
    {
        // Array to store constructed MST
        int parent[] = new int[V];
 
        // Key values used to pick minimum weight edge in cut
        int key[] = new int [V];
 
        // To represent set of vertices not yet included in MST
        Boolean mstSet[] = new Boolean[V];
 
        // Initialize all keys as INFINITE
        for (int i = 0; i < V; i++)
        {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }
        key[0] = 0;   
        parent[0] = -1; 
        for (int count = 0; count < V-1; count++)
        {
            int u = minKey(key, mstSet);
            mstSet[u] = true;
            for (int v = 0; v < V; v++)
                if (graph[u][v]!=0 && mstSet[v] == false &&
                    graph[u][v] <  key[v])
                {
                    parent[v]  = u;
                    key[v] = graph[u][v];
                }
        }
        printMST(parent, V, graph);
    }
 
    public static void main (String[] args)
    {
        /* Let us create the following graph
           2    3
        (0)--(1)--(2)
        |    / \   |
        6| 8/   \5 |7
        | /      \ |
        (3)-------(4)
             9          */
        prims t = new prims();
        int graph[][] = new int[][] {{0, 2, 0, 6, 0},
                                    {2, 0, 3, 8, 5},
                                    {0, 3, 0, 0, 7},
                                    {6, 8, 0, 0, 9},
                                    {0, 5, 7, 9, 0},
                                   };
 
        // Print the solution
        t.primMST(graph);
    }
}

The output of this program will be :

Hope this article will help you to understand the Prims Algorithm. If you are interested in programming do subscribe to our E-mail newsletter for all programming tutorials.