Prims Algorithm in Data Structure

(1456 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:

MST-PRIM (G, w, r) 1. for each u ? V [G] 2. do key [u] ? ? 3. ? [u] ? NIL 4. key [r] ? 0 5. Q ? V [G] 6. While Q ? ? 7. Do u ? EXTRACT - MIN (Q) 8. for each v ? Adj [u] 9. do the check if v ? Q and w (u, v) < key [v] 10. then ? [v] ? u 11. key [v] ? w (u, v)

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

Solution Worked 0 UpvotesUpvote

        

Solution Didn't Worked 1 DownvotesDownvote



Comments



Search

Play 2048 Game Online

Play Duckhunt Online

Need Help?

Looking for any Software or Tutorial?
Don't Worry, we will find it for you
Contact Now

Search Tags

    Prims Algorithm

    Prims Pseudocode

    Prims Flowchart