| 37 | // Function to construct and print MST for a graph represented |
| 38 | // using adjacency matrix representation |
| 39 | void primMST(int graph[][]) |
| 40 | { |
| 41 | // Array to store constructed MST |
| 42 | int parent[] = new int[V]; |
| 43 | |
| 44 | // Key values used to pick minimum weight edge in cut |
| 45 | int key[] = new int[V]; |
| 46 | |
| 47 | // To represent set of vertices included in MST |
| 48 | Boolean mstSet[] = new Boolean[V]; |
| 49 | |
| 50 | // Initialize all keys as INFINITE |
| 51 | for (int i = 0; i < V; i++) { |
| 52 | key[i] = Integer.MAX_VALUE; |
| 53 | mstSet[i] = false; |
| 54 | } |
| 55 | |
| 56 | // Always include first 1st vertex in MST. |
| 57 | key[0] = 0; // Make key 0 so that this vertex is |
| 58 | // picked as first vertex |
| 59 | parent[0] = -1; // First node is always root of MST |
| 60 | |
| 61 | // The MST will have V vertices |
| 62 | for (int count = 0; count < V - 1; count++) { |
| 63 | // Pick thd minimum key vertex from the set of vertices |
| 64 | // not yet included in MST |
| 65 | int u = minKey(key, mstSet); |
| 66 | |
| 67 | // Add the picked vertex to the MST Set |
| 68 | mstSet[u] = true; |
| 69 | |
| 70 | // Update key value and parent index of the adjacent |
| 71 | // vertices of the picked vertex. Consider only those |
| 72 | // vertices which are not yet included in MST |
| 73 | for (int v = 0; v < V; v++) |
| 74 | |
| 75 | // graph[u][v] is non zero only for adjacent vertices of m |
| 76 | // mstSet[v] is false for vertices not yet included in MST |
| 77 | // Update the key only if graph[u][v] is smaller than key[v] |
| 78 | if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) { |
| 79 | parent[v] = u; |
| 80 | key[v] = graph[u][v]; |
| 81 | } |
| 82 | } |
| 83 | |
| 84 | // print the constructed MST |
| 85 | printMST(parent, graph); |
| 86 | } |
| 87 | |
| 88 | public static void main(String[] args) |
| 89 | { |