月度归档: <span>2020年6月</span>
月度归档: 2020年6月

克鲁斯卡尔(Kruskal)算法求最小生成树

克鲁斯卡尔算法

克鲁斯卡尔算法,从边的角度求网的最小生成树,时间复杂度为O(nlogn)。和普里姆算法恰恰相反,更适合于求边稀疏的网的最小生成树

对于任意一个连通网的最小生成树来说,在要求总的权值最小的情况下,最直接的想法就是将连通网中的所有边按照权值大小进行升序排序,从小到大依次选择。

由于最小[……]

继续阅读