Prim

import java.util.*;

public class Prim {
    private static final class GNode implements Comparable<GNode> {
        // unique id of the node
        int id;
        // map of child nodes and their respective distance from current node 'id'
        Map<GNode, Integer> children = new HashMap<GNode, Integer>();
        // used in future computation, to store minimal/optimal updated distance
        int distFromParent = 10000;
        GNode parent = null;

        public GNode(int i, int dist) {
            this.id=i;
            this.distFromParent = dist;
        }

        public GNode(int i) {
            this.id=i;
        }

        @Override
        public int compareTo(GNode o) {
            if (this.distFromParent < o.distFromParent) {
                return -1;
            }

            if (this.distFromParent > o.distFromParent) {
                return 1;
            }

            return 0;
        }

        @Override
        public String toString() {
            return "GNode [id=" + id + ", distFromParent=" + distFromParent
                    + "]";
        }
    }

    public static class GNodeComparator implements Comparator<GNode>
    {
        @Override
        public int compare(GNode x, GNode y)
        {
            //return x.distFromParent - y.distFromParent;
            // Assume neither string is null. Real code should
            // probably be more robust
            // You could also just return x.length() - y.length(),
            // which would be more efficient.
            if (x.distFromParent < y.distFromParent)
            {
                return -1;
            }
            if (x.distFromParent > y.distFromParent)
            {
                return 1;
            }
            return 0;
        }
    }


    static String mstPrim(GNode[] nodes) {
        PriorityQueue<GNode> pq = new PriorityQueue<GNode>();
        //boolean[] visited = new boolean[nodes.length];
        //boolean[] exited = new boolean[nodes.length];
        String res = "";
        nodes[0].distFromParent = 0;
        for (int i = 0; i < nodes.length; i++) {
            pq.add(nodes[i]);
        }
        long sum = 0;
        int count = 0;
        while (!pq.isEmpty()) {
            for (GNode n : pq) {
                System.out.print(" " + n);
            }
            System.out.println();
            GNode u = pq.poll();
            for (GNode v : u.children.keySet()) {
                if (pq.contains(v) && u.children.get(v) < v.distFromParent) {
                    v.distFromParent = u.children.get(v);
                    v.parent = u;
                }
            }
            sum += u.distFromParent;
            if (!res.isEmpty()) res += " + ";
            if (count > 0) res += u.distFromParent;
            count++;
        }

        /*visited[0] = true;
        long sum = 0;
        int count = 0;
        while (pq.size() > 0) {
            for (GNode o :
                    pq) {
                System.out.print(o + " ");
            }
            System.out.println();
            GNode o = pq.poll();
            if (!exited[o.id]) {
                for (GNode n : o.children.keySet()) {
                    if (!exited[n.id]) {
                        if (visited[n.id]) {
                            if (n.distFromParent > o.children.get(n)) {
                                n.distFromParent = o.children.get(n);
                            }
                        } else {
                            visited[n.id] = true;
                            n.distFromParent = o.children.get(n);
                            //pq.add(n);
                        }
                    }
                }
                sum += o.distFromParent;
                if (!res.isEmpty()) res += " + ";
                if (count > 0) res += o.distFromParent;
                exited[o.id] = true;
                count++;
            }
           /* if (pq.size() == 0) {
                for (int i = 0; i < nodes.length; i++) {
                    if (!exited[i]) {
                        System.out.println(nodes[i]);
                        pq.add(nodes[i]);
                    }
                }
            }
        }*/
        return res + " = " + sum;
    }

    public static void start(int[] graph) {
        //Scanner in = new Scanner(System.in);
        //System.out.println("Enter graph:");
        int V = graph[0];
        int E = graph[1];
        int count = 2;
        int u, v, w;
        GNode[] nodes = new GNode[V];
        nodes[0] = new GNode(0);
        for (int i = 0; i < E; i++) {
            u = graph[count];
            count++;
            v = graph[count];
            count++;
            GNode un = nodes[u];
            GNode vn = nodes[v];
            if (un == null) {
                un = new GNode(u);
                nodes[u] = un;
            }
            if (vn == null) {
                vn = new GNode(v);
                nodes[v] = vn;
            }

            w = graph[count];
            count++;

            if (!(un.children.containsKey(vn) && un.children.get(vn) <= w))
                un.children.put(vn, w);
            if (!(vn.children.containsKey(un) && vn.children.get(un) <= w))
                vn.children.put(un, w);
        }
        String len = mstPrim(nodes);
        System.out.println("Min length (P): " + len);
    }
}