数据结构:
Kruskal算法的计算一个含V个顶点和E条边的连通加权无向图的最小生成树所需空间与E成正比,所需时间与ElogE成正比(最坏情况)。
方法:将边都添加进最小优先权队列中,每次从中取出最小的边,检查会不会与已经选出的边构成环(使用union-find算法),如果构成环,则弃掉这条边,否则将这条边加入最小生成树队列。循环执行直到最小优先权队列为空。
public class KruskalMST {
private Queue<Edge> mst; //用来保存最小代价生成树的队列
public KruskalMST(EdgeWeightedGraph G) {
mst = new Queue<Edge>();
MinPQ<Edge> pq = new MinPQ<Edge>(); //最小优先权队列
for(Edge e: G.edges())
pq.insert(e);//将所有边添加进优先队列
UF uf = new UF(G.V()); //union-find算法
while(!pq.isEmpty() && mst.size()<G.V()-1) {
Edge e = pq.delMin();//从优先队列得到最小的边
int v = e.either(),w = e.other(v);//得到最小边的顶点
if(uf.connected(v, w)) continue;//判断会不会构成环
uf.qu_union(v,w);//合并分量
mst.enqueue(e);//将边添加进树中
}
}
public Iterable<Edge> edges(){ return mst; }
}