What is Prims Algorithm?
It is a greedy algorithm. It starts with an empty spanning tree. The idea is to maintain the two sets of the vertices:
Contain vertices already included in MST(Minimum Spanning Tree).
Contain vertices not yet included.
At its every step, it considers all the edges and picks up the minimum weight edge. After picking the edge, it moves the other endpoint of edge to set containing MST.
Image Reference: Geeks for Geeks
Prims Flowchart:
Image Reference: Geeks for Geeks
Prims Pseudocode:
Prims Implementation in Java
<![CDATA[import java.util.*;
import java.lang.*;
import java.io.*;
class MST {
// Number of vertices in the graph
private static final int V = 5;
int minKey(int key[], Boolean mstSet[])
{
// Initialize min value
int min = Integer.MAX_VALUE, min_index = -1;
/* loop iteration */ 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 graph[][])
{
System.out.println("Edge \tWeight");
/* loop iterates */ for (int i = 1; i < V; i++)
System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
}
void primMST(int graph[][])
{
// Array to store constructed MST
int parent[] = new int[V];
int key[] = new int[V];
Boolean mstSet[] = new Boolean[V];
// Initialize all keys as INFINITE
/* loop iterates */for (int i = 0; i < V; i++) {
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
// Always include first 1st vertex in MST.
/*Key at 0 position is initiailised to zero */key[0] = 0;
/*Parent node */ parent[0] = -1;
// The MST will have V vertices
/* loop iterates */ for (int count = 0; count < V - 1; count++) {
// Pick thd minimum key vertex from the set of vertices
// not yet included in MST
int u = minKey(key, mstSet);
mstSet[u] = true;
/* loop iterates */ for (int v = 0; v < V; v++)
if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) /* Condition check */ {
parent[v] = u;
key[v] = graph[u][v];
}
}
// print the constructed MST
printMST(parent, 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 */
MST t = new MST();
/* Graph */ 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);
}
}
]]>
Output of the above program
<![CDATA[Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
]]>
1 Upvotes
4 Downvotes
