图的最小生成树C

1、西北师范大学地环学院地理信息系数据结构实验讲义十二 最小生成树张长城2011-2-8图的最小生成树，Prim算法，C语言实现实验任务描述1 有向含权图的存储设计；2 分析图的最小生成树的算法；3 C语言实现图的最小生成树。一、 有向图的存储和最小生成树算法分析1 Prim最小生成树对一个图而言，最小生成树的算法经常用到的是Prim算法。以下图为例：图 1 有向图的范例图Prim的算法，主要是构造两个集合：U、V，其中，U中有第0个顶点，V中有其余的顶点，一般编程中，设NO(NO=10000)为已经使用，则开始状态就是：V集合中，第0个元素是NO，代表已经放入U集合，其余的是顶点编号；U集合中，

2、第0个元素是0，代表第0个顶点在V集合。UV0NO,1,2,3,4,5表1 计算开始的状态在这个时候，考虑的第一步就是：从U中取到顶点编号、与V中的顶点中寻找最短距离的顶点，根据图1，则自然是到U中的0到V中的2、就是V1到V3，于是，把该顶点放入U集合，V集合中标记已经使用，就是：UV0,2NO,1,NO,3,4,5表2 找到第一个最小邻接顶点图中表示就是：图 2找到第一个最短邻接顶点U中有两个顶点，就是从U中逐个取0、2顶点，和V中各个顶点中对比，找到下一个最短距离的顶点，根据图1、不难发现是U中的2到V中的5，就是V3到V6。于是再次把5放入U集合，V中标记6已经使用，表处理如下：UV0

3、,2,5NO,1,NO,3,4,NO表3 找到第二个最小邻接顶点这个过程的结果就是相当于V3连接到V6，有下图： 图 3找到第二个最短邻接顶点注意表3，再次从U中逐个取出顶点、和V中未使用的顶点逐个对比，寻找最小路径的顶点，可以找到是U中的5到V中的3，就是V6到V4，于是表格再次处理如下：UV0,2,5,3NO,1,NO,NO,4,NO表4 找到第三个最小邻接顶点所生成的图就是： 图 4找到第三个最短邻接顶点由于表4中还有没使用的顶点，于是再次逐个从U中取顶点、逐个和V中的顶点对比，寻找最短路的顶点，不难发现有U中2到V中1、就是V3到V2距离最短，于是再次处理表4、成为：UV0,2,5,3

4、,1NO,NO,NO,NO,4,NO表5 找到第四个最小邻接顶点生成的图就是： 图 5找到第四个最短邻接顶点 最后，再次从U中逐个取顶点，寻找和V中顶点最小距离的顶点，就是1到4相当与V2到V5，处理表格5为：UV0,2,5,3,1,4NO,NO,NO,NO,NO,NO表6 找到第五个最小邻接顶点处理到图就是：图 6最终的最小生成树由于V集合中所有顶点都被使用了，所以程序到此停止。2 C语言的含权图的存储对含权图，其不连接数学上是无穷大，这在C语言中是无法实现的，所以一般用一个大数来表示，比如用1000，在上述图中，这个数字是足够了。所以这个邻接矩阵就是：A=图1的邻接矩阵这个写法表明：C语言

5、中的含权邻接矩阵和普通邻接矩阵没有什么差别，差别仅仅在程序处理中：一旦遇到一个指定的大数，则认为是不通的，由此可知对图的存储结构不需要做任何变动。3 C语言Prim最小生成树程序设计首先我们要有两个集合，用来表示U、V，对于大的图，最好使用链表，而对于我们这个简单的图，仅仅使用数组来表示就足够了。我们把图1中邻接矩阵的1000在C中定义为NO，这样方便后续的处理。开始，我们将在U数组中保存0，而在V数据中保存:NO、1、2、3、4，这代表着先把第0个顶点存进U集合，而第1、第2、第3.等后续的顶点在V集合，并且设置n变量记录进入U集合中的顶点个数，这样就完成了初始化操作。对于图，我们依然使用前

6、面的存储结构，所以图的顶点个数可以来自于G->num，而U、V的大小可以通过动态申请内存来完成。所以整个初始化工作可以用以下程序完成：12345678int *U,*V,i,j,n,min,a,b,ma,mb;U=(int *)malloc(sizeof(int)*G->num);V=(int *)malloc(sizeof(int)*G->num);for(i=0;i<G->num;i+)Ui=0;Vi=i;V0=NO;n=1;表7 PRIM最小生成树初始化 见P0.c下一步，就是要有函数来判断V集合中是否全部取空了，这个集合全部为空，就是说所有的值都是NO，为

7、此我们要编写一个函数来做判断，就是：1234567int VEmpty(int V,int n)int i;for(i=0;i<n;i+)if(Vi!=NO) return 0;return 1;表8 判断V集合中顶点是否全部取空 见P0.c完成这样的初始化后，则就是从U中取出一个顶点编号、逐个取出V中的顶点编号、然后寻找最短的路径，设置min开始是NO，第一步写成草稿就是：a=Ui; b=Vj;if (b=NO) 取下一个V中顶点; /说明这个顶点已经在U中if (G->pAab<min)min=G->pAab;ma=a;mb=b; /记录最小距离的两个顶点编号找到m

8、a、mb后，要把mb转入U，然后n+，就是：Un=mb; Vmb=NO;n+;于此同时打印顶点关系：printf("%s->%sn",G->pVma,G->pVmb);于是整个函数就是下表：写成一个完整的C语言程序就是：12345678910111213141516171819202122232425262728293031void Prim(struct Graph *G)int *U,*V,i,j,n,min,a,b,ma,mb;U=(int *)malloc(sizeof(int)*G->num);V=(int *)malloc(sizeof(

9、int)*G->num);for(i=0;i<G->num;i+)Ui=0;Vi=i;V0=NO;n=1;while(!VEmpty(V,G->num) min = NO;a=0;b=0;for(i=0;i<n;i+) for(j=0;j<G->num;j+)a=Ui; b=Vj;if (b=NO) continue; if (G->pAab<min)min=G->pAab;ma=a;mb=b;printf("%s->%sn",G->pVma,G->pVmb); Un=mb; Vmb=NO;n+;

10、free(U);free(V);表9 PRIM最小生成树初始化 见P0.c123456789101112131415161718main()int i,j;struct Graph *G;G=GraphCreat("p182G726.txt");printf("顶点名称:n");for(i=0;i<G->num;i+)printf("%st",G->pVi);printf("n邻接矩阵:n");for(i=0;i<G->num;i+) for(j=0;j<G->num;j+)printf("%dt",G->pAij);printf("