赤裸裸滴最小生成树（MST），刚学的玩意，用两种方法熟练一下。（都是greedy)
Kruskal方法：先对边按照代价非递减排序，再不断添加边且不产生环路，当边数=点数-1结束。判断加入（v，w）是否会产生环路，可以用并查集，如果检查v和w在同一集合中，说明这两个点已经连通，加入边（v, w）就会产生环路。Kruskal算法总时间复杂度O(eloge).Kru
阅读背景：
hdu 1233 还是畅通工程(最小生成树的Prim和Kruskal两种算法的c++实现)(prim算法详解)
来源：互联网
分享到：
