import java.util.Scanner;

public class Main {

    public static int prim(int[][] cost, int n) {
        int[] near = new int[n]; // Tracks the nearest vertices
        int[][] t = new int[n - 1][2]; // Array to store the edges of the minimum spanning tree
        int minCost = 0;

        // Step 1: Find the edge with minimum cost
        int k = -1, l = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (cost[i][j] < min) {
                    min = cost[i][j];
                    k = i;
                    l = j;
                }
            }
        }

        // Initialize the minimum cost and the first edge of the MST
        minCost += min;
        t[0][0] = k;
        t[0][1] = l;

        // Initialize the near array
        for (int i = 0; i < n; i++) {
            near[i] = (cost[i][l] < cost[i][k]) ? l : k;
        }
        near[k] = near[l] = -1; // Mark these vertices as part of the MST

        // Step 2: Find n - 2 edges to complete the MST
        for (int i = 1; i < n - 1; i++) {
            min = Integer.MAX_VALUE;
            int j = -1;

            // Find the vertex j with the minimum cost to add to the MST
            for (int m = 0; m < n; m++) {
                if (near[m] != -1 && cost[m][near[m]] < min) {
                    min = cost[m][near[m]];
                    j = m;
                }
            }

            // Add the edge to the MST
            t[i][0] = j;
            t[i][1] = near[j];
            minCost += cost[j][near[j]];
            near[j] = -1; // Mark j as included in the MST

            // Update the near array
            for (int m = 0; m < n; m++) {
                if (near[m] != -1 && cost[m][near[m]] > cost[m][j]) {
                    near[m] = j;
                }
            }
        }

        // Print the MST edges
        System.out.println("Edges in the Minimum Spanning Tree:");
        for (int i = 0; i < n - 1; i++) {
            System.out.println("(" + t[i][0] + ", " + t[i][1] + ")");
        }

        return minCost;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Take the number of vertices as input
        System.out.print("Enter the number of vertices: ");
        int n = sc.nextInt();

        // Create the adjacency matrix (cost) based on user input
        int[][] cost = new int[n][n];
        System.out.println("Enter the adjacency matrix (-1 for no edge):");

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    cost[i][j] = Integer.MAX_VALUE; // No self-loops
                } else {
                    System.out.print("Cost of edge between " + i + " and " + j + ": ");
                    int input = sc.nextInt();
                    cost[i][j] = (input == -1) ? Integer.MAX_VALUE : input;
                }
            }
        }

        // Calculate the minimum spanning tree
        int minCost = prim(cost, n);

        // Output the minimum cost of the MST
        System.out.println("Minimum Cost of the MST: " + minCost);
        sc.close();
    }
}

/*
Enter the number of vertices: 4
Enter the adjacency matrix (-1 for no edge):
Cost of edge between 0 and 1: 1
Cost of edge between 0 and 2: 3
Cost of edge between 0 and 3: -1
Cost of edge between 1 and 2: 1
Cost of edge between 1 and 3: 4
Cost of edge between 2 and 3: 2
Edges in the Minimum Spanning Tree:
(0, 1)
(1, 2)
(2, 3)
Minimum Cost of the MST: 4*/




 
Algorithm Prim(E, cost, n, t)
// E is the set of edges in G. cost[1 : n, 1 : n] is the cost
// adjacency matrix of an n vertex graph such that cost[i, j] is
// either a positive real number or ∞ if no edge (i, j) exists.
// A minimum spanning tree is computed and stored as a set of
// edges in the array t[1 : n − 1, 1 : 2]. (t[i, 1], t[i, 2]) is an edge in
// the minimum-cost spanning tree. The final cost is returned.
 
css
Copy code
Let (k, l) be an edge of minimum cost in E;  
mincost := cost[k, l];  
t[1, 1] := k; t[1, 2] := l;  
for i := 1 to n do  // Initialize near.  
{  
    if (cost[i, l] < cost[i, k]) then near[i] := l;  
    else near[i] := k;  
}  
near[k] := near[l] := 0;  
for i := 2 to n − 1 do  
{  
    // Find n − 2 additional edges for t.  
    Let j be an index such that near[j] ≠ 0 and  
    cost[j, near[j]] is minimum;  
    t[i, 1] := j; t[i, 2] := near[j];  
    mincost := mincost + cost[j, near[j]];  
    near[j] := 0;  
    for k := 1 to n do  // Update near[ ].  
    {  
        if ((near[k] ≠ 0) and (cost[k, near[k]] > cost[k, j]))  
            then near[k] := j;  
    }  
}  
return mincost;