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.

Prims Algorithm in Data Structure

Image Reference: Geeks for Geeks

Prims Flowchart:

Prims Algorithm in Data Structure Flowchart

Image Reference: Geeks for Geeks

Prims Pseudocode:

Prims Algorithm

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

Output of the above program

Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5
                 






Comments










Search Anything:

Sponsored Deals ends in



Technical Quizzes Specially For You:

Search Tags

    Prims Algorithm

    Prims Pseudocode

    Prims Flowchart

    Java code for Prims Algorithm