暑期集训之最小生成树总结 关于最小生成树的算法实现总结
——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;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] 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 w }line[MAX]; int Kruskal() { makeset(); //初始化集合 sort(line,line+edg); //按照路径的权值由小到大排序路径， int count=0; //记录边 int i=0,tx,ty; int sum=0； while(count 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. They're 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. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town. Input The first line of input is an integer T, which tells how many test cases followed. The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case. Output For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum. Sample Input 1 3 0 990 692 990 0 179 692 179 0 Sample Output 692 Hint Huge input,scanf is recommended. 题目大意就是找到最小生成树的最大的那个边，然后输出，题目比较简单，下面看看我的代码实现： #include struct Line //定义一个结构体，用来保存边 { int x; int y; int w; bool operator <(Line L)const{ return w }line[MAX]; int map[MMAX][MMAX]; int parent[MMAX],rank[MMAX]; int N,edg; void makeset() //集合初始化 { for(int i=0;i parent[i]=i; rank[i]=0; } } int findset(int x) //查找x元素属于哪个集合 { if(x==parent[x])return parent[x]; parent[x]=findset(parent[x]); //顺便路径压缩，以减少以后的findset（）过程 return parent[x]; } void Union_set(int x,int y) //合并俩个集合 { if(rank[x] parent[x]=y; else if(rank[x]>rank[y]) parent[y]=x; else{ parent[x]=y; rank[y]++; } } int Kruskal() { makeset(); sort(line,line+edg); int count=0; int i=0,tx,ty; int Max=-1; while(count tx=findset(line[i].x),ty=findset(line[i].y); if(tx!=ty) { count++; Union_set(tx,ty); Max=max(Max,line[i].w); } i++; } return Max; } void makeline() //根据输入的map产生路径，此处比较简单 { int i,j; edg=0; for(i=0;i for(j=0;j if(i!=j) { line[edg].x=i; line[edg].y=j; line[edg].w=map[i][j]; 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库最小生成树总结在线全文阅读。
相关推荐：