kruskal算法构造最小生成树

kruskal算法构造最小生成树

1.问题
假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：
每次找权值最小的边，将连接两条边的顶点加入集合U中，构造最小生成树。

2.解析

（1）图中有6个顶点v1-v6，每条边的边权值都在图上；由图可知，v2-v3这条边权值最小，所以选择它为起始边。U={v1，v3}； E={(v1,v3)}；
（2）现在继续查找权值最小的边，如图所示，通过图中我们可以看到边v4-v6的权值最小为2，那么将v4，v6 加入到U集合，（v4，v6）加入到E，状态如下：
U={v1，v3，v4,v6}； E={（v1，v3）,(v4,v6)}；
（3）继续寻找，现在状态为U={v1，v3，v4,v6}； E={（v1，v3）,(v4,v6)}；在相交的边上查找最小值。
我们可以找到最小的权值为（v2，v5）=4，那么我们将v2,v5加入到U集合，并将最小边加入到TE集合，那么加入后状态如下：
U={v1，v3，v4,v6,v2,v5}； E={（v1，v3），（v4，v6）,(v2,v5)}； 如此循环一下直到找到所有顶点并且相互连通为止。

3.设计

4.分析
时间复杂度：O（nlogn) (n为边数）

5.源码地址
https://github.com/ylx1234/prim-kruskal