Prims

import java.util.Scanner;

public class Prims {
    private static int N;  // Number of vertices
    
    // Function to get the vertex with the minimum cost that is not yet in MST
    public static int getMin(int[] costs, boolean[] isInMST) {
        int min = Integer.MAX_VALUE;
        int minVertex = -1;
        
        // Iterate over all vertices to find the one with the minimum cost
        for (int i = 0; i < costs.length; i++) {
            if (!isInMST[i] && costs[i] < min) {  // Only consider vertices not in MST
                min = costs[i];
                minVertex = i;
            }
        }
        return minVertex;
    }
    
    // Function to perform Prim's algorithm to find the MST
    public static void solution(int[][] matrix) {
        int[] parent = new int[N];  // To store the parent of each vertex in MST
        int[] costs = new int[N];   // To store the minimum cost for each vertex
        boolean[] isInMST = new boolean[N];  // To check if a vertex is in MST
        
        // Initialize all costs to infinity, and mark all vertices as not in MST
        for (int i = 0; i < N; i++) {
            costs[i] = Integer.MAX_VALUE;
            isInMST[i] = false;
        }
        
        // The starting vertex (0) has cost 0, and no parent
        costs[0] = 0;
        parent[0] = -1;
        
        // Run Prim's algorithm to find the MST
        for (int i = 0; i < N - 1; i++) {
            int curr = getMin(costs, isInMST);  // Get the vertex with the minimum cost
            isInMST[curr] = true;  // Add it to the MST
            
            // Update the costs of the adjacent vertices
            for (int adj = 0; adj < N; adj++) {
                // If there is an edge, and the vertex is not in MST, and the cost is smaller
                if (matrix[curr][adj] != 0 && !isInMST[adj] && matrix[curr][adj] < costs[adj]) {
                    parent[adj] = curr;  // Set the parent
                    costs[adj] = matrix[curr][adj];  // Update the cost
                }
            }
        }
        
        // Print the results (the MST edges and total cost)
        printResults(parent, matrix);
    }
    
    // Function to print the edges and their weights
    public static void printResults(int[] parent, int[][] matrix) {
        int totalCost = 0;
        System.out.println("Edge\tWeight");
        
        // Print each edge in the MST
        for (int i = 1; i < N; i++) {
            System.out.println(parent[i] + " - " + i + " \t" + matrix[i][parent[i]]);
            totalCost += matrix[i][parent[i]];  // Add the edge weight to the total cost
        }
        System.out.println("Total cost of MST: " + totalCost);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // Read the number of vertices
        System.out.print("Enter the number of vertices: ");
        N = sc.nextInt();
        
        // Initialize the adjacency matrix
        int[][] matrix = new int[N][N];
        
        System.out.println("Enter the adjacency matrix (0 for no edge):");
        // Read the adjacency matrix from the user
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        
        // Call Prim's algorithm to find the MST
        solution(matrix);
        
        // Close the scanner
        sc.close();
    }
}