Prims Algorithm in Data Structure

[2366 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
        

Algorithm Logic Test

Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once. 



Need any help in Programming? Chat with Us

Comments



Online Compiler
Search
Algorithm Quiz

Only 5% Users were able to score above 75% in this Quiz. Can You Crack this?

Deals Ends in





Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Search Tags

    Prims Algorithm

    Prims Pseudocode

    Prims Flowchart

    Java code for Prims Algorithm