- 首页
- 计算机考试
- 计算机技术与软件水平考试
- 报考指南
- 正文
2012年软考程序员考试考前知识点复习指导（6）
2012年计算机软件水平考试强化阶段，计算机软件水平考试网特整理了有关考试辅导资料，便于考生复习参考。以下是关于2012年软考程序员考试考前知识点复习指导
最小生成树之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 <(const Edge & a,const Edge & b)
{
return a.cost
}
/*