首页 > 代码库 > 算法8-4:Kruskal算法
算法8-4:Kruskal算法
Kruskal算法用于计算一个图的最小生成树。这个算法的步骤如下:
按照边的权重从小到达进行排序
依次将每条边增加到最小生成树中,除非这条边会造成回路
实现思路
第一个步骤需要对边进行排序,排序方法在之前的章节中已经介绍了很多,可以使用优先级队列进行实现,也可以使用归并排序进行实现,这里采用归并排序。
第二个步骤需要判断是否会造成回路。如果增加一条边会形成回路,那么这条边在增加之前,它两端的顶点必定是能够连通的。因此,在算法中使用并查集实现高效的判断。
代码
import java.util.LinkedList; import java.util.Queue; public class KruskalMST { private Queue<Edge> mst = new LinkedList<Edge>(); public KruskalMST(EdgeWeightedGraph G) { // 先对边进行排序 Edge[] edges = new Edge[G.E()]; int i = 0; for (Edge e : G.edges()) { edges[i] = e; i++; } MergeSort.sort(edges); // 使用并查集判断顶点是否连接 UnionFind uf = new UnionFind(G.V()); for (Edge e : edges) { int v = e.either(); int w = e.other(v); if (!uf.connected(v, w)) { uf.union(v, w); mst.add(e); } } } public Iterable<Edge> edges() { return mst; } public double weight() { double result = 0; for (Edge e : mst) { result += e.weight(); } return result; } }
复杂度
上面的代码复杂度和图中边的数量有关,最坏情况下的复杂度为E logE。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。