实验5 最小生成树
一、实验目的
1．进一步掌握图的结构及非线性特点，递归特点和动态性。
2．进一步巩固最小生成树的两种求解算法。
二、实验原理
构造最小生成树（MST）就是找出权值最小的生成树。
思想：从顶点 v0 开始，选择离 v0 最近顶点 v1 构成树 T1 ，再连接与 T1 最近顶点 v2 构成树 T2， 如此重复直到所有顶点均在所构成树中为止。
遵循原则：
1、尽可能选取权值小的边，但不能构成回路；
2、选取n－1条恰当的边以连通n个顶点
首先明确：
利用 lowcost[ ] 数组记录距离此顶点最近的权值；G[i][j] 存储从文件中读入的两边距离；
Closeset[i] 记录顶点i与哪个顶点相依附（因为J一直记录当前最新加入到生成树的顶点，所以这个closeset[i]就等于j）；j 一直记录与当前顶点距离最小的顶点；
Prim() 函数：
首先把lowcost[ ] 中的数据初始化为顶点0 到其他顶点的距离，把closeset[j]置为0（即：顶点i都依附于0顶点）
进入循环：循环vcount-1次（最后一个顶点直接放到最后，不用比较）
第一次：
1. 第一次就是找出距离顶点0最近的顶点，通过比较lowcost[i]，找最小
2. 找到距离顶点0 最近的顶点 j 后，把总距离加上当前G[ j ][father[ j ];输出两个顶点和他们之间的距离G[j][father[j]]
3. 初始化lowcost[i]，等于顶点J到各个顶点i的距离，closeset[j]置为J
第二次：
1. 从顶点j到其他顶点的距离中找到最小值，通过比较lowcost[i],找最小
2. 找到了距离最近的顶点 j 后，把总距离加上当前G[ J ][father[ j ];输出两个顶点和他们之间的距离G[J][father[j]]
3. 初始化lowcost[i],等于顶点j到各个顶点i的距离，closeset[j]置为j
第三次
..
..
…
第vcount-1次
最终把所以顶点都连接起来，构造好了最小生成树，输出最小权值之和。
应用：要连通n个城市需要n－1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。
三、参考程序
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#define infinity 1000000
#define max_vertexes 6 // 定义图形中顶点的个数
typedef int Graph[max_vertexes][max_vertexes];// 边上的权值
void prim(Graph G,int vcount,int father[]){
int i,j,k;
int lowcost[max_vertexes];//最小代价边上的权值
int closeset[max_vertexes],used[max_vertexes];//依附在U中的顶点；标记是否已被选中
int min;
int result=0;//记录最短距离的和
//首先从顶点0开始，初始化数据
for (i=0;i<vcount;i++){ //初始化所有数组，把最短距离初始化为其他顶点到1结点的距离
lowcost[i]=G[0][i];
closeset[i]=0;
used[i]=0;
father[i]=-1;
}
used[0]=1;
printf("%s %s %s\n","前顶点","后顶点","距离");
//循环VCOUNT-1次，//从lowcost[i]中找到最小值并把此结点加入生成树
for (i=0;i<vcount-1;i++){
j=0;
min = infinity;
for (k=1;k<vcount;k++)
if ((!used[k])&&(lowcost[k]<min)){
min = lowcost[k];
j=k;//j一直记录最近结点
}
//找到J，使两个依附，并输出
father[j]=closeset[j]; //构造两顶点依附
printf(" %d %d ",father[j]+1,j+1);//输出当前找到的结点，及该顶点依附的上一个结点
printf(" %d\n",G[j][father[j]]);//输出这两个顶点之间距离
result=result+G[j][father[j]];
used[j]=1;//把第j个顶点并入了U中,记录j顶点已被用
//初始化，从当前刚找到的顶点J出发，确定所有未加入生成树的顶点到此顶点J的距离，这样下次循环时，就是从这些数据中找最小值了
for (k=1;k<vcount;k++)
if (!used[k]&&(G[j][k]<lowcost[k])){//保留到k的最短路径
lowcost[k]=G[j][k];
closeset[k]=j;
}
}
printf("权值之和：%d",result);
}
int main()
{
FILE *fr;
int i,j,weight;
Graph G;
int father[max_vertexes];
//初始化顶点间的距离
for(i=0; i<max_vertexes;i++)
for(j=0; j<max_vertexes;j++)
G[i][j] = infinity;
fr = fopen("prim.txt","r");
if(!fr){
printf("fopen failed\n");
exit(1);
}
//把读入的数据，对应各位给赋给各个顶点间距离
while(fscanf(fr,"%d%d%d", &i, &j, &weight) != EOF){
G[i-1][j-1] = weight;
G[j-1][i-1] = weight;
}
prim(G,max_vertexes,father);//根据prim算法构造最小生成树
return 0;
}
}
prim.txt中的内容:
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
5 6 6
4 6 2