Prims algorithm

import java.util.Scanner;

class PrimsAlgorithm {
    private static int V;

    int minKey(int key[], boolean mstSet[]) {
        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;
    }

    void printMST(int parent[], int graph[][]) {
        int totalCost = 0;
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
            totalCost += graph[i][parent[i]];
        }
        System.out.println("Total cost of the MST: " + totalCost);
    }

    void primMST(int graph[][]) {
        int parent[] = new int[V];
        int key[] = new int[V];
        boolean mstSet[] = new boolean[V];

        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;

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

        printMST(parent, graph);
    }

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

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

        int[][] graph = new int[V][V];

        System.out.println("Enter the adjacency matrix (enter 0 if there is no edge between two vertices):");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }

        PrimsAlgorithm t = new PrimsAlgorithm();
        t.primMST(graph);

        scanner.close();
    }
}




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;