数据结构19————图的最小生成树Prim&Kruskal
一. 目录
二. 最小生成树的概念
1.最小生成树的概念
- 生成树:连通图的极小连通子图称为图的生成树,显然顶点数为n 的连通图, 生成树边数为n-1;
- 从连通图中某一顶点出发遍历图时,图中所有的顶点加上遍历时经过的边所构成的子图T, 恰好就是一棵生成树
- 最小生成树：生成树各边权值之和为生成树代价，其代价最小的生成树为最小生成树。
- 最小生成树有两种算法:普利姆(Prim)算法&克鲁斯卡尔(Kruskal)算法
2.最小生成树的应用
设在 n 个城市之间建立通讯网, 则要连通 n 个城市最少需要修建 n-1条线路，现要拿出最节省经费的通讯网建设方案。
假设无向图的每条边表示两城市之间一条线路, 权值表示修建费用, 则该问题归结为求权值之和最小的生成树问题。
3.最小生成树的性质
设 N=（V,{E}）是一个连通图，U是V的非空子集，若(u,v)是满足u，且v∈V-U的具有最小权值的边,则必存在一棵包含(u,v)的最小生成树。
三. 普利姆(Prim)算法
1.思想
在所有已连通的点中，寻找由这些点组成的边中权值最小的边，并且这个边可以连接一个新的点(还未连通)。那么这个的边就是最小生成树的一部分，将这个新的点标记为已连通。重复上述过程，直到所有点均连通。
形式化表述
设N=(V,{E})是连通网，prim算法步骤为：
（1）初始U={u0}(u0∈V),TE=φ；
（2）在所有u∈U, v∈V-U的边中选一条代价最小的边（u0，v0）并入集合 TE，同时将v0并入U；
（3）重复（2）,直到U=V,TE含有n-1条边。此时T=(V,{TE})为N的最小生成树
总的来说是从一个初始点出发，根据这个点延伸的边，每次连通一个点。直到把所有点全部连通。
2.演示
3.代码
//Prim算法求最小生成树
void MiniSpanTree_Prim(AdjMatrix *G){
int min,i,j,k;
int adjvex[MAXVEX];//保存相关顶点下标
int lowcost[MAXVEX];//保存相关顶点的权值
lowcost[0]=0; //初始化第一个权值为0，即v0加入生成树中
adjvex[0]=0; //初始化第一个顶点下标为0
for(i=1;i<G->vexnum;i++){
lowcost[i]=G->acre[0][i]; //将与v0顶点相关点的权值存入lowcost数组中
adjvex[i]=0; //都初始化为vo的下标
}
for(i=1;i<G->vexnum;i++){
min = INFINITY; //初始化权值为无穷
j=1;k=0;
//寻找当前权值最小的边
while(j<G->vexnum){
if(lowcost[j]!=0&&lowcost[j]<min){//如果权值不为0切小于min
min = lowcost[j];
k=j;
}
j++;
}
printf("(%c,%c)",G->Vex[adjvex[k]],G->Vex[k]);//打印当前顶点中权值最小的边
lowcost[k]=0;//将当前顶点的权值置为0，表示完成任务
//更新lowcost和adjvex数组
for(j=1;j<G->vexnum;j++){
if(lowcost[j]!=0&&G->acre[k][j]<lowcost[j]){
lowcost[j]=G->acre[k][j];
adjvex[j]=k;
}
}
}
} 
四. 克鲁斯卡尔(Kruskal)算法
1.思想
将所有边按照权值从小到大排序，然后依次从小到大，将可以连通新节点的边纳入最小生成树中
形式化表述
假设N=(V,{E})是连通网
（1）将n个顶点看成n个集合；
（2）按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；
（3）重复（2）,直到所有的顶点在同一顶点集合内。
总的来说:为使生成树边的权值之和达到最小,则尽可能地选取权值小的边作为生成树中的边.
2.演示
3.代码
int Find(int *parent,int f){
while(parent[f]>0){
f = parent[f];
}
return f;
}
void MiniSpanTree_Kruskal(AdjList *G){
int i,n,m;
ArcNode edges[MAXVEX]; //定义边集数组
int parent[MAXVEX]={0};//定义一数组来判断边与边是否形成环路
sort(G,edges);//将G中的边赋给edges，并按权值从小到大排序
for(i=0;i<G->arcnum;i++){
n=Find(parent,edges[i].begin);
m=Find(parent,edges[i].end);
if(n!=m){ //如果n和m不相等，说明此边没有与现有生成树形成环路
parent[n]=m; //将此边的结尾顶点放在下标为n的parent，表示已经放入到生成树集合中
printf("(%c,%c)",G->vertex[edges[i].begin],G->vertex[edges[i].end]);
}
}
}
五. 源代码地址
六. 参考资料
《大话数据结构》
《数据结构与算法》