2011年软考程序员考试复习笔试知识点整理(11)

 15、最小生成树之kruskal算法

　　最小生成树两个重要的算法：Prim 和 Kruskal。

　　Prim：时间复杂度O(n^2)，适用于边稠密的网络。

　　Kruskal：时间复杂度为O(e*log(e))，适用于边稀疏的网络。

　　kruskal算法的时间复杂度主要由排序方法决定，其排序算法只与带权边的个数有关，与图中顶点的个数无关，当使用时间复杂度为O(eloge)的排序算法时，克鲁斯卡算法的时间复杂度即为O(eloge)，因此当带权图的顶点个数较多而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果最好!Kruskal

　　从所有边中找到一个最小的边，且将改变放入后不会生成圈，重复n-1次后求出最小生成树。我们首先将所有边排序，然后从小到大判断，如果不产生圈就加入树中，当加入n-1条边时停止。为了判断是否组成圈，我们要用到并查集，相关知识可以在本站或任一本竞赛书中找到，这里不赘述。算法复杂度是(eloge+eα)，α是做一次并查集的复杂度，可以认为是常数。

　　/*

　　并查集的一个特性:

　　用一个数组p[]表示每一个元素的父级元素

　　最父级的元素的父级元素是一个负数,这个负数的绝对值是这个集合下的元素的个数

　　*/

　　#include

　　#include

　　usingnamespace std;

　　constint N=1001; //定义能处理的最大点的个数

　　template

　　structEdge

　　{

　　int from;

　　int to;

　　T cost;

　　};

　　template

　　booloperator