Using Prim's Algorithm, starting at vertex A, find the
Minimal Spanning Tree (MST) for the weighted graph
G in figure 4.2 below.
A
10
6
D
7
3
B
C
E
6
3
4
5
4
1
2
9
H
1
F
G

Question

Accepted Answer

```java // Importing necessary libraries import java.util.Arrays; // Class to represent the Prim's Algorithm for MST public class PrimsAlgorithm { // Method to find the vertex with minimum key value, from the set of vertices not yet included in MST private static int minKey(int[] key, Boolean[] mstSet, int vertices) { // Initialize min value int min = Integer.MAX_VALUE, minIndex = -1; for (int v = 0; v < vertices; v++) if (!mstSet[v] && key[v] < min) { min = key[v]; minIndex = v; } return minIndex; } // Function to construct and print MST for a graph represented using adjacency matrix representation public static void primMST(int[][] graph) { // Number of vertices in the graph int vertices = graph.length; // Array to store constructed MST int[] parent = new int[vertices]; // Key values used to pick minimum weight edge in cut int[] key = new int[vertices]; // To represent set of vertices not yet included in MST Boolean[] mstSet = new Boolean[vertices]; // Initialize all keys as INFINITE for (int i = 0; i < vertices; 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 vertices for (int count = 0; count < vertices - 1; count++) { // Pick the minimum key vertex from the set of vertices not yet included in MST int u = minKey(key, mstSet, vertices); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of the adjacent vertices of the picked vertex. for (int v = 0; v < vertices; v++) // graph[u][v] is non-zero only for adjacent vertices of m // mstSet[v] is false for vertices not yet included in MST // Update the key only if graph[u][v] is smaller than key[v] if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) { parent[v] = u; key[v] = graph[u][v]; } } // Print the constructed MST printMST(parent, graph); } // A utility function to print the constructed MST stored in parent[] private static void printMST(int[] parent, int[][] graph) { System.out.println("Edge Weight"); for (int i = 1; i < graph.length; i++) System.out.println(parent[i] + " - " + i + " " + graph[i][parent[i]]); } // Driver method public static void main(String[] args) { /* Let us create the following graph 2 3 (0)--(1)--(2) | / \ | 6| 8/ \5 |7 | / \ | (3)-------(4) 9 */ int graph[][] = new int[][]{{0, 6, 0, 2, 0}, {6, 0, 3, 8, 5}, {0, 3, 0, 0, 7}, {2, 8, 0, 0, 9}, {0, 5, 7, 9, 0}}; // Print the solution primMST(graph); } } ``` ∻Explanation∻ ⚹This Java code implements Prim's Algorithm to find the Minimal Spanning Tree (MST) of a given weighted graph. The `primMST` method constructs the MST using an adjacency matrix representation of the graph. The `minKey` method is used to find the vertex with the minimum key value that is not already included in the MST. The `printMST` method prints the edges included in the MST along with their weights. The `main` method provides a sample graph to test the algorithm.⚹ ∻Step-by-step Instruction∻ ‖ ▪ ⋮ Define the `minKey` method to find the minimum key value for the vertices not yet included in the MST. ‖ ‖ ▪ ⋮ Define the `primMST` method to construct the MST using the adjacency matrix representation of the graph. ‖ ‖ ▪ ⋮ Initialize all keys as infinite and set the first vertex's key to 0 to start the MST from the first vertex. ‖ ‖ ▪ ⋮ Use a loop to find and add the minimum key vertex to the MST set and update the keys of its adjacent vertices. ‖ ‖ ▪ ⋮ Define the `printMST` method to print the constructed MST showing the edges and their weights. ‖ ‖ ▪ ⋮ In the `main` method, create a sample graph and call the `primMST` method to print the MST. ‖ ∻Time Complexity∻ ⚹The time complexity of Prim's Algorithm is O(V^2) where V is the number of vertices in the graph, as we are using an adjacency matrix representation and searching for the minimum key vertex in every iteration.⚹ ∻Space Complexity∻ ⚹The space complexity is O(V) as we are maintaining arrays to store the keys, the MST set, and the parent of each vertex in the MST.⚹

Sia