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.
edge : 0-1 edge : 1-4 edge : 4-2 edge : 1-3
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.
