数据结构 最小生成树

时间:2022-10-01 11:39:09

实验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