PrimsAlgorithm

import java.util.*;

public class PrimsAlgorithm {

    // A utility method to print the resulting MST
    public static void printMST(int[] parent, int[][] graph, int V) {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
        }
    }

    // A utility method to find the vertex with the minimum key value
    public static int minKey(int[] key, boolean[] mstSet, int V) {
        int min = Integer.MAX_VALUE, minIndex = -1;

        for (int v = 0; v < V; v++) {
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    // Function to implement Prim's algorithm
    public static void primMST(int[][] graph, int V) {
        // Array to store the MST
        int[] parent = new int[V];
        // Key values used to pick the minimum weight edge
        int[] key = new int[V];
        // To track vertices included in MST
        boolean[] mstSet = new boolean[V];

        // Initialize all keys as infinity and mstSet[] as false
        Arrays.fill(key, Integer.MAX_VALUE);
        Arrays.fill(mstSet, false);
        key[0] = 0; // Start with the first vertex
        parent[0] = -1; // The first node is the root of the MST

        // Run Prim's algorithm
        for (int count = 0; count < V - 1; count++) {
            // Pick the minimum key vertex from the set of vertices not yet included in MST
            int u = minKey(key, mstSet, V);

            // Include the picked vertex in 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 < V; v++) {
                // graph[u][v] is non-zero only for adjacent vertices of u
                // mstSet[v] is false for vertices not yet included in MST
                // Update the key and parent if the weight of edge u-v is less than the current key value of v
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    key[v] = graph[u][v];
                    parent[v] = u;
                }
            }
        }

        // Print the constructed MST
        printMST(parent, graph, V);
    }

    public static void main(String[] args) {
        // Input: number of vertices (V) and the graph as an adjacency matrix
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of vertices: ");
        int V = scanner.nextInt();

        int[][] graph = new int[V][V];
        System.out.println("Enter the adjacency matrix (use 0 for no edge):");

        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }

        // Run Prim's algorithm to find the Minimum Spanning Tree
        primMST(graph, V);

        scanner.close();
    }
}

i/p

Enter the number of vertices: 5
Enter the adjacency matrix (use 0 for no edge):
0 2 0 6 0
2 0 3 8 5
0 3 0 0 7
6 8 0 9 0
0 5 7 0 0

o/p

Edge    Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5