package Famous;

import java.util.*;

/**
 * @author zhengstars
 * @date 2023/12/09
 */


public class Prim {

    /**
     * Number of vertices in the graph
     */
    private int V;
    /**
     * Adjacency list to represent the graph
     */
    private List<List<Edge>> adj;

    /**
     * Constructor to initialize the graph
     * @param V
     */
    public Prim(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    /**
     * Function to add an undirected edge to the graph
     * @param u
     * @param v
     * @param weight
     */
    public void addEdge(int u, int v, int weight) {
        adj.get(u).add(new Edge(v, weight));
        adj.get(v).add(new Edge(u, weight));
    }

    /**
     * Function to perform Prim's algorithm and find the minimum spanning tree
     */
    public void primMST() {
        // Priority queue to store edges based on their weights
        PriorityQueue<Edge> minHeap = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        // Array to keep track of visited vertices
        boolean[] visited = new boolean[V];

        // Variable to store the total weight of the minimum spanning tree
        int minCost = 0;

        // Start with the first vertex
        minHeap.add(new Edge(0, 0));

        while (!minHeap.isEmpty()) {
            // Extract the edge with the minimum weight
            Edge edge = minHeap.poll();
            int u = edge.dest;

            // Skip if the vertex is already included in MST
            if (visited[u]) {
                continue;
            }

            // Include vertex in MST
            visited[u] = true;
            minCost += edge.weight;

            // Add adjacent edges of the removed vertex to the priority queue
            for (Edge neighbor : adj.get(u)) {
                if (!visited[neighbor.dest]) {
                    minHeap.add(neighbor);
                }
            }
        }

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

    /**
     * Inner class to represent an edge in the graph
     */
    private static class Edge {
        int dest;
        int weight;

        // Constructor to initialize an edge with destination and weight
        public Edge(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }

    /**
     * Main method to test the Prim's algorithm
     * @param args
     */
    public static void main(String[] args) {
        int V = 5;
        Prim graph = new Prim(V);

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

        // Run Prim's algorithm and print the result
        graph.primMST();
    }
}