问在java中实现kruskals算法

EN

Edge class something like this:

class Edge implements Comparable<Edge>
{
    int v1,v2,wt; 

    Edge(int v1, int v2, int wt)
    {
        this.v1=v1;
        this.v2=v2;
        this.wt=wt;
    }

    @Override
    public int compareTo(Edge o) {
        Edge e1 = (Edge)o;
        if(e1.wt==this.wt)
            return 0;
        return e1.wt < this.wt ? 1 : -1;
    }

    @Override
    public String toString()
    {
        return String.format("Vertex1:%d \t Vertex2:%d \t Cost:%d\n", v1,v2,wt);

    }
}

HashMap<Integer,Set<Integer>> forest = new HashMap<Integer,Set<Integer>>();
for(Integer vertex : vertices)
{
        //Each set stores the known vertices reachable from this vertex
        //initialize with it self.
    Set<Integer> vs = new HashSet<Integer>();
    vs.add(vertex);
    forest.put(vertex, vs);
}

//sort your edges, you should use existing functionality where possible, saves testing needed
//here edges is your Stack, pop until minimum spanning tree is found.
Collections.sort(edges);
ArrayList<Edge> minSpanTree = new ArrayList<Edge>();
while(true) //while you haven't visited all the vertices at least once
{
    Edge check = edges.remove(0);//pop

    Set<Integer> visited1 = forest.get(check.v1);
    Set<Integer> visited2 = forest.get(check.v2);
    if(visited1.equals(visited2))
        continue;
    minSpanTree.add(check);
    visited1.addAll(visited2);
    for(Integer i : visited1)
    {
        forest.put(i, visited1);
    }
    if(visited1.size()==vertices.length)
        break;
}

/**
 * An implementation of Kruskal's MST algorithm using an edge list.
 * @author William Fiset
 **/

// Union find data structure 
class UnionFind {

  private int[] id, sz;

  public UnionFind(int n) {
    id = new int[n];
    sz = new int[n];
    for (int i = 0; i < n; i++) {
      id[i] = i;
      sz[i] = 1;
    }
  }

  public int find(int p) {
    int root = p;
    while (root != id[root])
      root = id[root];
    while (p != root) { // Do path compression
      int next = id[p];
      id[p] = root;
      p = next;
    }
    return root;
  }

  public boolean connected(int p, int q) {
    return find(p) == find(q);
  }

  public int size(int p) {
    return sz[find(p)];
  }

  public void union(int p, int q) {
    int root1 = find(p);
    int root2 = find(q);
    if (root1 == root2) return;
    if (sz[root1] < sz[root2]) {
      sz[root2] += sz[root1];
      id[root1] = root2;
    } else {
      sz[root1] += sz[root2];
      id[root2] = root1;
    }
  }

}

class Edge implements Comparable <Edge> {
  int from, to, cost;
  public Edge(int from, int to, int cost) {
    this.from = from;
    this.to = to;
    this.cost = cost;
  }
  @Override public int compareTo(Edge other) {
    return cost - other.cost;
  }
}

public class KruskalsEdgeList {

  // Given a graph represented as an edge list this method finds
  // the Minimum Spanning Tree (MST) cost if there exists 
  // a MST, otherwise it returns null.
  static Long kruskals(Edge[] edges, int n) {

    if (edges == null) return null;

    long sum = 0L;
    java.util.Arrays.sort(edges);
    UnionFind uf = new UnionFind(n);

    for (Edge edge : edges) {

      // Skip this edge to avoid creating a cycle in MST
      if (uf.connected(edge.from, edge.to))
        continue;

      // Include this edge
      uf.union(edge.from, edge.to);
      sum += edge.cost;

      // Optimization to stop early if we found
      // a MST that includes all the nodes
      if (uf.size(0) == n) break;

    }

    // Make sure we have a MST that includes all the nodes
    if (uf.size(0) != n) return null;

    return sum;

  }

}