kruskalmst.java

来自「个人学习图算法时写的源码 包括最小生成树, 最大网络流, DSF遍历, BSF」· Java 代码 · 共 30 行

package twf.weightedgraph.undirected;

import java.util.Arrays;

import twf.adt.UF;
import twf.weightedgraph.Edge;
import twf.weightedgraph.EdgeComparator;
import twf.weightedgraph.Graph;
import twf.weightedgraph.common.GraphUtilities;

public class KruskalMST {
	 private int V;
	  private UF uf;
	  private Edge[] a, mst;
	  public KruskalMST(Graph G)
	    { int v, w, E;
	      E = G.E(); V = G.V();
	      mst = new Edge[V];
	      uf = new UF(V);
	      a = GraphUtilities.edges(G);
	      Arrays.sort(a, new EdgeComparator());
	      for (int i = 0, k = 1; i < E && k < V; i++)
	        if (!uf.find(v = a[i].v(), w = a[i].w()))
	          { uf.unite(v, w); mst[k++] = a[i]; }
	    }
	  public Edge[] mst() {
		  return mst;
	  }
}