克鲁斯卡尔(Kruskal)算法求最小生成树
克鲁斯卡尔算法
克鲁斯卡尔算法，从边的角度求网的最小生成树，时间复杂度为O(nlogn)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。
对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。
由于最小[……]
生成树
Prim算法构建最小生成树
最小生成树
最小生成树(minimum spanning tree)是由n个顶点, n-1条边, 将一个连通图连接起来, 且使权值最小的结构。
最小生成树可以用Prim(普里姆)算法或kruskal(克鲁斯卡尔)算法求出。
Prim（普里姆）算法
- 时间复杂度：O(N^2)（N为顶点数）
- prim算[……]