《[计算机]最小生成树Kruskal算法.doc》由会员分享，可在线阅读，更多相关《[计算机]最小生成树Kruskal算法.doc（9页珍藏版）》请在三一文库上搜索。
1、1、 题目描述： 如图所示的赋权图表示某七个城市及预算它们之间的一些某些直接通信道路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小并计算其最小值。二、题目分析：该题即要求赋权图的最小生成树，即可使得各城市间互相通信又使造价费用最小。1.生成树及最小生成树定义 (1)生成树的定义入下： 对于有n个顶点的无向连通图G，把遍历过程中顺序访问的两个顶点之间的路径记录下来，这样G中的n个顶点以及由出发点一次访问其余n-1个顶点所经过的n-1条边就构成了G的极小连通子图，也就是G的一棵生成树，出发顶点是生成树的根。 (2)下面给出最小生成树的概念：给定一个连通网络，要求构造
2、具有最小代价的生成树时，也即使生成树的各边的权值总和达到最小。把生成树各边的权值总和定义为生成树的权，那么具有最小权值的生成树就构成了连通网络的最小生成树。2.最小生成树的性质构造最小生成树的算法有很多种，其中大多数的算法都利用了最小生成树的一个性质，简称为MST性质：假设G=（V，E）是一个连通网络，U是V中的一个真子集，若存在顶点和顶点的边(u，v)是一条具有最小权值的边，则必存在G的一棵最小生成树包括这条边(u，v)。3.常用算法及思想利用该性质构造最小生成树的常用算法主要有：Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法。(1)Prim算法思想： 设G=（V,E）是一个有n个
3、顶点的连通图，用T=(U，TE)表示要构造的最小生成树，其中U为顶点集合，TE为边的集合。则Prim算法的具体步骤描述入下：初始化：令U=，TE=。从V中取出一个顶点放入生成树的顶点集U中，作为第一个顶点，此时；从，的边(u，v)中找一条代价最小的边，将其放入TE中，并将放入U中；重复步骤（2），直至U=V为止。此时集合TE中必有n-1条边，T即为所要构造的最小生成树。(2)Kruskal算法思想： 设G=（V,E）是一个有n个顶点的连通图，则令最小生成树的初始状态为只有n个顶点而无任何边的非连通图T=V,图中每个顶点自成一个连通分量。依次选择E中的最小代价边，若该边依附于T中的两个不同的连通
4、分量，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。以此类推，直到T中所有顶点都在同一连通分量上为止。这时的T就是G的一棵最小生成树。三、方案解决：在本题中我们将采用Kruskal算法来构造最小生成树。从题目所给赋权图中我们可以得到该图的邻接矩阵为：我们将题中的赋权图中i,j两个城市之间的造价费用边记为，则从小到大排序如下：顺序123456789101112边费用13491516172023252836则构造步骤如下：1. 开始构造前，令T=V,，Cost=0如图所示：2. 从图中选择造价最小的边，即为，此时T=2,3,4,5,6，造价Cost=1 如图所示： 3. 接着选择造价
5、第二小的序号2的边，即，加入T中，此时T=2,5,6,，造价Cost=1+3=4如图所示：4. 接着选择造价第三小的序号3的边，即，加入T中，此时T=5,6,，此时Cost=4+4=8 如图所示：5. 接着选择造价第四小的序号4的边，即，加入T中，此时T=5,6,，Cost=8+9=17如图所示：6. 选择造价第五小的序号为5的边，即，由于加入后边，将构成回路，因此舍弃该边如图所示：7. 选择造价第六小的序号为6的边，即，由于加入后边，将构成回路，因此舍弃该边如图所示：8. 选择造价第七小的序号为7的边，即，加入T中，此时T=6,，Cost=17+17=34如图所示：9. 接着选择造价第八小的
6、序号8的边，即，由于加入后边，将构成回路，因此舍弃该边如图所示：10. 选择造价第九小的序号为9的边，即，加入T中，此时T=,，Cost=34+23=57如图所示：11.算法结束 此时，所有顶点已包含在树中，整棵最小生成树已经构造完成。即应该在城市（1,7），（2,7），（3,7），（3,4），（4,5），（1,6）之间建造通信道路，可使得城市间相互通信又造价费用最小，此时可以得到其最小的费用为57万元四、Kruskal算法程序1.程序代码如下：#include#include#define M 20#define MAX 20/结构体定义typedef struct int begin;in
7、t end;int weight;edge;typedef structint adj;int weight;AdjMatrixMAXMAX;typedef structAdjMatrix arc;int vexnum, arcnum;MGraph;/函数申明 void CreatGraph(MGraph *);void sort(edge* ,MGraph *);void MiniSpanTree(MGraph *);int Find(int *, int );void Swapn(edge *, int, int);void CreatGraph(MGraph *G)/构造图int i,
8、j,n, m;printf(请输入城市数及边数:);scanf(%d %d,&G-vexnum,&G-arcnum);for (i = 1; i vexnum; i+)/初始化图for ( j = 1; j vexnum; j+)G-arcij.adj = G-arcji.adj = 0; printf(请输入有道路连通的2个城市及他们之间的造价费用(城市1 城市2 费用):n);for ( i = 1; i arcnum; i+)/输入边和费用scanf(%d %d,&n,&m);G-arcnm.adj = G-arcmn.adj = 1;scanf(%d,&G-arcnm.weight);
9、printf(邻接矩阵为:n);for ( i = 1; i vexnum; i+) for ( j = 1; j vexnum; j+)if(G-arcij.adj=1)printf(%d ,G-arcij.weight);else printf(%d ,G-arcij.adj);G-arcji.weight=G-arcij.weight;printf(n);void sort(edge edges,MGraph *G)/对权值进行排序 int i, j;for ( i = 1; i arcnum; i+)for ( j = i + 1; j arcnum; j+)if (edgesi.we
10、ight edgesj.weight)Swapn(edges, i, j);printf(按造价排序之后的边顺序为(序号 边 费用):n);for (i = 1; i arcnum; i+)printf(%d. %dn, i,edgesi.begin, edgesi.end, edgesi.weight);void Swapn(edge *edges,int i, int j) int temp; temp = edgesi.begin; edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end; edgesi.en
11、d = edgesj.end; edgesj.end = temp; temp = edgesi.weight; edgesi.weight = edgesj.weight; edgesj.weight = temp; void MiniSpanTree(MGraph *G)/生成最小生成树 int i, j, n, m,Mincost=0; int k = 1; int parentM;edge edgesM;for ( i = 1; i vexnum; i+)for (j = i + 1; j vexnum; j+)if (G-arcij.adj = 1)edgesk.begin = i;
12、edgesk.end = j;edgesk.weight = G-arcij.weight;k+;sort(edges, G);for (i = 1; i arcnum; i+)parenti = 0;printf(最小生成树为:n);for (i = 1; i arcnum; i+)/核心部分 n = Find(parent, edgesi.begin);m = Find(parent, edgesi.end);if (n != m)parentn = m;printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);Mincost+=edgesi.weight;printf(使各城市间能够通信的最小费用为：Mincost=%dn,Mincost);int Find(int *parent, int f)while ( parentf 0)f = parentf;return f;void main()/主函数 MGraph *G;G = (MGraph*)malloc(sizeof(MGraph);CreatGraph(G);MiniSpanTree(G); 2.程序运行结果：- 9 -