最小生成树总结.doc

暑期集训之最小生成树总结 关于最小生成树的算法实现总结 ——Kruskal算法和prim算法的实现 Kruskal算法 咱们先看一下Kruskal算法，此算法是并查集的经典运用，所以要深入了解这个算法，就得了解并查集。并查集的概念以及它的实现我就不再说了，简要介绍一下它几个基本的操作，主要就有三个：makeset(),findset(),Union_set()，就这三个基本的操作，下面看看代码实现。 定义一个parent[MAX]数组，parent[i]用来保存元素i属于哪个集合，初始化为本身；再定义一个rank[MAX]数组，rank[i]用来保存的元素i的级别，初始化为0； makeset()函数： void makeset() //也相当于初始化，既是对parent[MAX]和rank[MAX]数组初始化 { for(int i=0;iN;i++) { parent[i]=i; rank[i]=0; } } findset()函数，接受一个参数i，返回查询i属于哪个集合。 int findset(int x) { if(x==parent[x])return parent[x]; parent[x]=findset(parent[x]); //此处用到了路径压缩 return parent[x]; } Union_set()函数接受俩个参数x和y，既是合并集合x和y。 void Union_set(int x,int y) { if(rank[x]rank[y]) //将短的一个作为长的一个子女 parent[x]=y; else if(rank[x]rank[y]) parent[y]=x; else{ parent[x]=y; //两个相同是随便，但是后面的rank记得加加。 rank[y]++; } } 下面就看看Kruskal算法了： 路径的定义： struct Line //定义一个结构体，用来保存边 { int x; int y; int w; bool operator (Line L)const{ return wL.w; } }line[MAX]; int Kruskal() { makeset(); //初始化集合 sort(line,line+edg); //按照路径的权值由小到大排序路径， int count=0; //记录边 int i=0,tx,ty; int sum=0； while(countN-1) //有N个顶点，则最小生成树只有N-1条边 { tx=findset(line[i].x),ty=findset(line[i].y); if(tx!=ty) //检查边是否在集合中 { count++; Union_set(tx,ty); //不在集合中就添加到集合中 sum+=line[i].w; } i++; } return sum; } 下面看一道题目，是我在poj上做的，就是用Kruskal算法实现的，题目如下： Highways Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9864 Accepted: 4624 Description The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. Theyre planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system. Flatopian towns are numbered from 1 to N. E