PrimMST.java

import java.util.*;

class Graph {
    private int V; // Number of vertices
    private List<List<Edge>> adjacencyList;

    Graph(int V) {
        this.V = V;
        adjacencyList = new ArrayList<>(V);
        for (int i = 0; i < V; ++i)
            adjacencyList.add(new ArrayList<>());
    }

    void addEdge(int u, int v, int weight) {
        Edge edge1 = new Edge(u, v, weight);
        Edge edge2 = new Edge(v, u, weight);
        adjacencyList.get(u).add(edge1);
        adjacencyList.get(v).add(edge2);
    }

    void primMST() {
        boolean[] visited = new boolean[V];
        int[] parent = new int[V];
        int[] key = new int[V];
        Arrays.fill(key, Integer.MAX_VALUE);

        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(V, Comparator.comparingInt(node -> node.key));
        priorityQueue.add(new Node(0, 0)); // Add the source vertex with key 0
        key[0] = 0;

        while (!priorityQueue.isEmpty()) {
            int u = priorityQueue.poll().vertex;
            visited[u] = true;

            for (Edge edge : adjacencyList.get(u)) {
                int v = edge.destination;
                int weight = edge.weight;
                if (!visited[v] && weight < key[v]) {
                    priorityQueue.removeIf(node -> node.vertex == v);
                    key[v] = weight;
                    parent[v] = u;
                    priorityQueue.add(new Node(v, weight));
                }
            }
        }

        System.out.println("Best Minimum Spanning Tree:");
        for (int i = 1; i < V; ++i)
            System.out.println(parent[i] + " - " + i);
    }

    class Node {
        int vertex;
        int key;

        Node(int vertex, int key) {
            this.vertex = vertex;
            this.key = key;
        }
    }

    class Edge {
        int source;
        int destination;
        int weight;

        Edge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
    }
}

public class PrimMST {
    public static void main(String[] args) {
        int V = 5; // Number of vertices
        Graph graph = new Graph(V);

        // Adding edges to the graph
        graph.addEdge(0, 1, 2);
        graph.addEdge(0, 3, 6);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3, 8);
        graph.addEdge(1, 4, 5);
        graph.addEdge(2, 4, 7);
        graph.addEdge(3, 4, 9);

        graph.primMST();
    }
}