Lab Programs

import java.util.*;

public class PGraph {
    public void Prim(int graph[][], int V) {
        // Initialize INF as max value
        int INF = 999999999;
        // Initialize no of edges it is always less than V-1
        int no_edges;
        // Initialize boolean array with 'false'
        boolean selected[] = new boolean[V];
        Arrays.fill(selected, false);

        // Currently no of edges is 0
        no_edges = 0;
        // And selected first element is true
        selected[0] = true;

        System.out.println("Edge:   Weight");
        // Loop Untill no of edges is smaller than V-1
        int weight = 0;
        while (no_edges < V - 1) {
            // Initialize min to infinite
            int min = INF;
            int x = 0, y = 0;

            for (int i = 0; i < V; i++) {
                if (selected[i] == true) {
                    for (int j = 0; j < V; j++) {
                        if (selected[j] == false && graph[i][j] != 0) {
                            if (min > graph[i][j]) {
                                min = graph[i][j];
                                x = i;
                                y = j;
                            }
                        }

                    }
                }
            }
            System.out.println(x + " - " + y + " : " + graph[x][y]);
            weight += graph[x][y];

            selected[y] = true;
            no_edges++;
        }
        System.out.println("Weight of the graph: " + weight);
    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        PGraph p = new PGraph();
        System.out.println("Enter no. of vertices: ");
        int V = scan.nextInt();
        int[][] graph = new int[V][V];
        System.out.println("Enter graph: ");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                graph[i][j] = scan.nextInt();
            }
        }
        p.Prim(graph, V);
    }
}