Prim's algorithm to find a minimum spanning tree in Java

A minimum spanning tree aka minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph. This subset connects all the vertices together, without any cycles and with the minimum possible total edge weight.

There can be more than one minimum spanning tree for a graph. The overall cost, however, will be the same for different MSTs of the same tree.

Prim’s Algorithm

Prim’s algorithm is a greedy algorithm that finds the MST for a weighted undirected graph.

The algorithm proceeds by building MST one vertex at a time, from an arbitrary starting vertex. At each step, it makes the most cost-effective choice. That is, it optimizes locally to achieve a global optimum.

The way Prim’s algorithm works is as follows :

Initialize the minimum spanning tree with a random vertex (initial vertex).
Find all the edges that connect the tree to new vertices, find the minimum, and add it to the tree (greedy choice).
Keep repeating step 2 until we get a minimum spanning tree (until all vertices are reached).

We can look at an example to understand how Prim’s algorithm works.

Let the weighted undirected graph be as follows :

We choose 0 as the initial vertex.

As the next step, we choose the minimum from all the nodes connected with the MST.

At each subsequent stage, we find the minimum-cost edge that connects the tree to a new vertex.

Using 4 edges we’ve connected all the 5 nodes. The cost of the minimum spanning tree is the sum of all the edge weights.

In this example, it is :

4+1+6+2 = 13

Prim’s Algorithm Java Code

The java implementation is as follows.

Code for Graph class :

package com.JournalDev;
import java.util.*;
public class Graph
{
    
      // Representation of the graph 
      
    private static int infinite = 9999999;

    int[][]  LinkCost; // graph matrix
    int      num_nodes; // number of nodes 
    
    // constructor takes in a matrix as its input 
    Graph(int[][] mat)
    {
        int i, j;

        num_nodes = mat.length;

        LinkCost = new int[num_nodes][num_nodes];

        // copying the weights to LinkCost matrix
        for ( i=0; i < num_nodes; i++)
        {
            for ( j=0; j < num_nodes; j++)
            {
                LinkCost[i][j] = mat[i][j];

                if ( LinkCost[i][j] == 0 )
                    LinkCost[i][j] = infinite;
            }
        }
    }

    //function to get the nodes that are unreached
    public int unReached(boolean[] r)
    {
        boolean done = true;

        for ( int i = 0; i < r.length; i++ )
            if ( r[i] == false )
                return i;

        return -1;
    }


    public void Prim( )
    {
        int i, j, k, x, y;

        boolean[] Reached = new boolean[num_nodes];	// array to keep track of the reached nodes
        int[] predNode = new int[num_nodes];		// array to maintain min cost edge

// starting vertex
        Reached[0] = true;
        //setting other vertices as unreached
        for ( k = 1; k < num_nodes; k++ )
        {
            Reached[k] = false;
        }

        predNode[0] = 0;      // No edge for node 0

        printCoveredNodes( Reached );

     //we iterate for n-1 nodes that haven't been reached yet
        for (k = 1; k < num_nodes; k++)
        {
            x = y = 0;

            for ( i = 0; i < num_nodes; i++ )
                for ( j = 0; j < num_nodes; j++ )
                {
//update the MST with the minimum cost Link
                    if ( Reached[i] && !Reached[j] &&
                            LinkCost[i][j] < LinkCost[x][y] )
                    {
                        x = i;
                        y = j;
                    }
                }

            System.out.println("Next selected edge: (" +
                    + x + "," +
                    + y + ")" +
                    " cost = " + LinkCost[x][y]);


            predNode[y] = x;          // add the min cost link to predNode
            Reached[y] = true;

            printCoveredNodes( Reached );
            System.out.println();
        }

        printMinCostEdges( predNode );
    }
    // function to print the edges of spanning tree
    void printMinCostEdges( int[] a )
    {
 System.out.println("Edges in MST: ");
        for ( int i = 0; i < num_nodes; i++ )
            System.out.println( a[i] + " --> " + i );
    }

   
 void printCoveredNodes(boolean[] Reached )
    {
        System.out.print("Covered Nodes = ");
        for (int i = 0; i < Reached.length; i++ )
            if ( Reached[i] )
                System.out.print( i + " ");
        System.out.println();
    }

}

Main class :

package com.JournalDev;

public class Main {

    public static void main(String[] args) {
        int[][] conn = {{0, 4, 0, 0, 5},
                {4, 0, 3, 6, 1},
                {0, 3, 0, 6, 2},
                {0, 6, 6, 0, 7},
                {5, 1, 2, 7, 0},
        };

        Graph G = new Graph(conn);

        G.Prim();
    }
}

Output

We can verify the output using the example above.

Conclusion

This tutorial was on Prim’s algorithm to find out the minimum spanning tree for undirected weighted graphs. Hope you enjoyed learning about Prim’s algorithm.

Prim’s algorithm to find a minimum spanning tree in Java

Prim’s Algorithm

Prim’s Algorithm Java Code

Output

Conclusion

Leave a Reply Cancel reply