Prims Algorithm in Data Structure

[8212 views]

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:

Prims Algorithm in Data Structure Flowchart

Image Reference: Geeks for Geeks

Prims Pseudocode:

Prims Implementation in Java

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); } }