Need help implementing Kruskal\'s algorithm in java shoul mirror the pseudocode:

Question

Need help implementing Kruskal's algorithm in java

shoul mirror the pseudocode:

KRUSKAL(V, E,w)
A ? ?
for each vertex v ? V
do MAKE-SET(v)
sort E into nondecreasing order by weight w
for each (u, v) taken from the sorted list
do if FIND-SET(u) = FIND-SET(v)
then A ? A ? {(u, v)}
UNION(u, v)
return A

need methods MAKESET UNION FINDSET and MST_KRUSKAL.

Any help is greatly appreciated

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;
import java.util.ArrayList;

public class KruskalAlgo {
int MAX_VALUE = Integer.MAX_VALUE;
int INFINITY = 11000;
Scanner scanner = new Scanner(System.in);
Graph G = new Graph();
public Set<Set<Node>> nodeSet = new HashSet<Set<Node>>(); // set of sets of nodes for Kruskal's algorithm

public static void main(String args[]) {
   new Program3().run();
}

public Graph MST_KRUSKAL(Graph G) {
   //Kruskal's algorithmpublic class

}

// utility functions for sets of nodes
public Set<Node> UNION(Node u, Node v) {
   // implement UNION here
}

public Set<Node> MAKESET(Node u) {
   // implement MAKESET here
}

  
public Set<Node> FINDSET(Node u) {
   // implement FINDSET here
}
  

public void run() {
   // process input, first line is number of nodes, followed by number of edges,
   // then each line has one edge, with tail first, then head, then weight
int numNodes = scanner.nextInt();
int numEdges = scanner.nextInt();
   //System.out.println("numNodes="+numNodes+" numEdges="+numEdges);
   // create the nodes
   for(int j = 1; j <= numNodes ; j++) {
   //System.out.println("added node "+j);
   Node n = G.addNode();
   }

   // process the edges in the input;
   for (int j = 1; j <= numEdges; j++) {
   int headNum = scanner.nextInt();
   int tailNum = scanner.nextInt();
   int weight = scanner.nextInt();
   //System.out.println("added edge head="+headNum+" tail="+tailNum);
   Node head = G.nodeList.get(headNum);
   Node tail = G.nodeList.get(tailNum);
   G.addEdge(head,tail,weight);
}

// test print it out
   //G.print();
   Graph T = MST_KRUSKAL(G); // compute the MST by Kruskal's agorithm

   T.print(); // generate output
}

}

Explanation / Answer

public class KruskalMST {
    private double w;
    private Queue<Edge> mst = new Queue<Edge>();
  
    public KruskalMST(Graph G) {
                MinPQ<Edge> pq = new MinPQ<Edge>();
        for (Edge e : G.edges()) {
            pq.insert(e);
        }

    
        UF uf = new UF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.delMin();
            int v = e.either();
            int w = e.other(v);
            if (u.connected(v, w)) {
                u.union(v, w);
                mst.enqueue(e);
                weight += e.weight();
            }
        }
        assert check(G);
    }

  
    public Iterable<Edge> edges() {
        return mst;
    }

  
    public double weight() {
        return weight;
    }
    private boolean check(Graph G) {
        double total = 0.0;
        for (Edge e : edges()) {
            total += e.weight();
        }
        double EPSILON = 1E-12;
        if (Math.abs(total - weight()) > EPSILON)
       {
System.err.printf("Weight does not equal weight(): %f vs. %f ", total, weight());
            return false;
        }
        U u = new UF(G.V());
        for (Edge e : edges()) {
            int v = e.either(), w = e.other(v);
            if (u.connected(v, w)) {
                System.err.println("Not a forest");
                return false;
            }
            u.union(v, w);
        }
        for (Edge e : G.edges()) {
            int v = e.either(), w = e.other(v);
            if (!u.connected(v, w)) {
                System.err.println("Not a spanning forest");
                return false;
            }
        }

      
        for (Edge e : edges()) {

                        u = new UF(G.V());
            for (Edge f : mst) {
                int i = f.either(), j = f.other(x);
                if (f != e) u.union(x, y);
            }
          
         
            for (Edge f : G.edges()) {
                int i = f.either(), j = f.other(x);
                if (!u.connected i,j)) {
                    if (f.w() < e.w()) {
                        System.err.println("Edge " + f + " violates cut");
                        return false;
                    }
                }
            }

        }

        return true;
    }

  
    public static void main(String[] args) {
        In in = new In(args[0]);
        EdgeWeightedGraph G = new EdgeWeightedGraph(in);
        KruskalMST mst = new KruskalMST(G);
        for (Edge e : mst.edges()) {
            StdOut.println(e);
        }
        StdOut.printf("%.5f ", mst.w());
    }

}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.