ADA_LAB4!!!!

package graphalgo;

import graphs.Edge;
import graphs.ISimpleGraph;
import graphs.UndirectedGraph;

import java.util.HashSet;
import java.util.Set;

import priorityqueues.MyPriorityQueue;
import priorityqueues.PriorityQueueImpl;

public class PrimMSTFinderWithPriorityQueue implements IMSTFinder {
    private double Q[];
    private boolean mark[];
    private Edge[] parent;
    private int N;


    public Set<Edge> FindMST(UndirectedGraph g) {

//      System.out.println("PrimMSTFinderWithPriorityQueue - not yet implemented");
            //return null;
            N = g.getNrNodes();

            mark = new boolean[N];
            PriorityQueueImpl Q = new PriorityQueueImpl(N);



            parent = new Edge[N];
            for (int v = 0; v < N; v++) {
                parent[v] = null;
                //Q[v] = Double.POSITIVE_INFINITY;
                mark[v] = false;
            }

            int root=0; // any node can be picked as root
            doPrim(g, root);

            Set<Edge> result = new HashSet<Edge>();
            for (int v = 0; v < N; v++) {
                if (parent[v] != null) {
                    result.add(parent[v]);
                    }
        }
            return result;
    }

    private int extractMin() {
        double valmin = Double.POSITIVE_INFINITY;
        int indmin = -1;
        for (int i = 0; i < N; i++)
            if (!mark[i]){  // select the minimum distance node, from the
                            // nodes that are still not marked
                if (Q[i] <= valmin) { // compares for smaller OR EQUAL
                                         // to handle unconnected graphs
                    valmin = Q[i];
                    indmin = i;
                }
            }
        mark[indmin]=true;
        Q[indmin]=0;
        return indmin;
    }
private void doPrim(ISimpleGraph g1, Integer root){

    Q[root] = 0;
    int iter=0;
    while  (iter<N){ // iterate until all N nodes are added to the MST
        iter++;

        int u = extractMin();

        for (Edge e : g1.edgesOutgoingFrom(u)) {
            int v = e.other(u);
            if (Q[v] > e.weight()) {
                parent[v] = e;
                Q[v]= e.weight();
}


            }}}}