Flashcards
Prim's MST
Cards in this deck (1)
- 1import java.util.*; import java.lang.*; import java.io.*; https://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/ class MST { // Number of vertices in the graph private static final int V=5; // A utility function to find the vertex with minimum key int minKey(int key[], Boolean mstSet[]) { // Initialize min value int min = Integer.MAX_VALUE, min_index=-1; for (int v = 0; v < V; v++) if (mstSet[v] == false && key[v] < min) { min = key[v]; min_index = v; } return min_index; } // A utility function to print the constructed MST stored in // parent[] void printMST(int parent[], int n, int graph[][]) { System.out.println("Edge Weight"); for (int i = 1; i < V; i++) System.out.println(parent[i]+" - "+ i+" "+ graph[i][parent[i]]); }void primMST(int graph[][])
{
int parent[] = new int[V];
int key[] = new int [V];
Boolean mstSet[] = new Boolean[V];
for (int i = 0; i < V; i++)
{
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
// Always include first 1st vertex in MST.
key[0] = 0; // Make key 0 so that this vertex is
// picked as first vertex
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (int count = 0; count < V-1; count++)
{
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v]!=0 && mstSet[v] == false &&
graph[u][v] < key[v])
{
parent[v] = u;
key[v] = graph[u][v];
}
}
printMST(parent, V, graph);
}
Information
- Description
- Flashcards on Prim's MST, created by Suhas S on 18/05/2018.
- Created by
- Suhas S · May 2018
- Updated
- May 18, 2018
- Views
- 0
- Rating