9512.net
甜梦文库
当前位置:首页 >> IT/计算机 >>

最小生成树(Kruskal算法)


一、题目描述:
如图所示的赋权图表示某七个城市及预算它们之间的一些某些直接通信道路造价(单 位:万元) ,试给出一个设计方案,使得各城市之间既能够通信又使总造价最小并计算其最 小值。

二、题目分析:
该题即要求赋权图的最小生成树,即可使得各城市间互相通信又使造价费用最小。 1.生成树及最小生成树定义 (1)生成树的定义入下: 对于有 n 个顶点的无向连通图 G, 把遍历过程中顺序访问的两个顶点之间的路径记录下 来, 这样 G 中的 n 个顶点以及由出发点一次访问其余 n-1 个顶点所经过的 n-1 条边就构成了 G 的极小连通子图,也就是 G 的一棵生成树,出发顶点是生成树的根。 (2)下面给出最小生成树的概念: 给定一个连通网络, 要求构造具有最小代价的生成树时, 也即使生成树的各边的权值总 和达到最小。 把生成树各边的权值总和定义为生成树的权, 那么具有最小权值的生成树就构 成了连通网络的最小生成树。 2.最小生成树的性质 构造最小生成树的算法有很多种,其中大多数的算法都利用了最小生成树的一个性质, 简称为 MST 性质:假设 G=(V,E)是一个连通网络,U 是 V 中的一个真子集,若存在顶 点 u ∈ U 和顶点 v ∈ (V ? U ) 的边(u,v)是一条具有最小权值的边,则必存在 G 的一棵最小 生成树包括这条边(u,v)。 3.常用算法及思想 利用该性质构造最小生成树的常用算法主要有: Prim(普里姆)算法和 Kruskal(克鲁斯卡 尔)算法。 (1)Prim 算法思想: 设 G=(V,E )是一个有 n 个顶点的连通图,用 T=(U,TE)表示要构造的最小生成树, 其 中 U 为顶点集合,TE 为边的集合。则 Prim 算法的具体步骤描述入下:

?初始化:令 U={?},TE={?}。从 V 中取出一个顶点 u0 放入生成树的顶点集 U 中,作为
-1-

第一个顶点,此时 T = ({u0 }, {φ }) ;

?从 u ∈ U , v ∈ (V ? U ) 的边(u,v)中找一条代价最小的边 (u * , v* ) ,将其放入 TE 中,并
将 v 放入 U 中;
*

?重复步骤(2) ,直至 U=V 为止。此时集合 TE 中必有 n-1 条边,T 即为所要构造的最小生
成树。 (2)Kruskal 算法思想: 设 G=(V,E )是一个有 n 个顶点的连通图,则令最小生成树的初始状态为只有 n 个顶点 而无任何边的非连通图 T={V,{?}},图中每个顶点自成一个连通分量。依次选择 E 中的最小 代价边,若该边依附于 T 中的两个不同的连通分量,则将此边加入到 T 中;否则,舍去此 边而选择下一条代价最小的边。以此类推,直到 T 中所有顶点都在同一连通分量上为止。 这时的 T 就是 G 的一棵最小生成树。

三、方案解决:
在本题中我们将采用 Kruskal 算法来构造最小生成树。 从题目所给赋权图中我们可以得到该图的邻接矩阵为:

? 0 20 0 0 0 23 1 ? ?20 0 15 0 0 0 4 ? ? ? ? 0 15 0 3 0 0 9 ? ? ? G = ? 0 0 3 0 17 0 16 ? ? 0 0 0 17 0 28 25? ? ? ? 23 0 0 0 28 0 36? ? 1 4 9 16 25 36 0 ? ? ?
我们将题中的赋权图中 i,j 两个城市之间的造价费用边记为 S ij ,则从小到大排序如下: 顺序 边 费用 1 2 3 4 5 6 7 8 9 10 11 12

S17
1

S34
3

S 27
4

S37
9

S 23
15

S 47
16

S 45
17

S12
20

S16
23

S57
25

S56
28

S 67
36

则构造步骤如下: 1.开始构造前,令 T={V,{?}},Cost=0 如图所示:

-2-

2.从图中选择造价最小的边,即为 S17 ,此时 T={{2,3,4,5,6},{ S17 }},造价 Cost=1 如图所示:

3.接着选择造价第二小的序号 2 的边,即 S34 ,加入 T 中,此时 T={{2,5,6},{ S17 , S34 }},造 价 Cost=1+3=4 如图所示:

4.接着选择造价第三小的序号 3 的边,即 S 27 ,加入 T 中,此时 T={{5,6},{ S17 , S34 , S 27 }} 此时 Cost=4+4=8 如图所示:

5.接着选择造价第四小的序号 4 的边, 即 S37 , 加入 T 中, 此时 T={{5,6},{ S17 , S34 , S 27 , S37 }}, Cost=8+9=17 如图所示:

-3-

6.选择造价第五小的序号为 5 的边,即 S 23 ,由于加入后边 S 23 , S 27 , S37 将构成回路,因此 舍弃该边 如图所示:

7.选择造价第六小的序号为 6 的边,即 S 47 ,由于加入后边 S34 , S37 , S 47 将构成回路,因此 舍弃该边 如图所示:

8.选择造价第七小的序号为 7 的边,即 S 45 ,加入 T 中,此时 T={{6},{ S17 , S34 , S 27 , S37 ,

S 45 }},Cost=17+17=34
如图所示:

9.接着选择造价第八小的序号 8 的边,即 S12 ,由于加入后边 S12 , S 27 , S17 将构成回路,因 此舍弃该边 如图所示:

-4-

10.选择造价第九小的序号为 9 的边,即 S16 ,加入 T 中,此时 T={{?},{ S17 , S34 , S 27 , S37 ,

S 45 , S16 }},Cost=34+23=57
如图所示:

11.算法结束 此时,所有顶点已包含在树中,整棵最小生成树已经构造完成。即应该在城市{(1,7) , (2,7) , (3,7) , (3,4) , (4,5) , (1,6)}之间建造通信道路,可使得城市间相互通信又造价费 用最小,此时可以得到其最小的费用为 57 万元

四、Kruskal 算法程序
1.程序代码如下: #include<stdio.h> #include<stdlib.h> #define M 20 #define MAX 20 //结构体定义 typedef struct { int begin; int end; int weight; }edge; typedef struct { int adj; int weight; }AdjMatrix[MAX][MAX]; typedef struct { AdjMatrix arc; int vexnum, arcnum; }MGraph;

-5-

//函数申明 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, j,n, m; printf("请输入城市数及边数:"); scanf("%d %d",&G->vexnum,&G->arcnum); for (i = 1; i <= G->vexnum; i++)//初始化图 { for ( j = 1; j <= G->vexnum; j++) { G->arc[i][j].adj = G->arc[j][i].adj = 0; } } printf(" 请输入有道路连通的 2 个城市及他们之间的造价费用 ( 城市 1 用):\n"); for ( i = 1; i <= G->arcnum; i++)//输入边和费用 { scanf("%d %d",&n,&m); G->arc[n][m].adj = G->arc[m][n].adj = 1; scanf("%d",&G->arc[n][m].weight); } printf("邻接矩阵为:\n"); for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { if(G->arc[i][j].adj==1) printf("%d ",G->arc[i][j].weight); else printf("%d ",G->arc[i][j].adj); G->arc[j][i].weight=G->arc[i][j].weight; } printf("\n"); } } void sort(edge edges[],MGraph *G)//对权值进行排序 { int i, j;

城市 2



-6-

for ( i = 1; i < G->arcnum; i++) { for ( j = i + 1; j <= G->arcnum; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } } printf("按造价排序之后的边顺序为(序号 边 费用):\n"); for (i = 1; i <= G->arcnum; i++) { printf("%d. < %d, %d > %d\n", i,edges[i].begin, edges[i].end, edges[i].weight); } } void Swapn(edge *edges,int i, int j) { int temp; temp = edges[i].begin; edges[i].begin = edges[j].begin; edges[j].begin = temp; temp = edges[i].end; edges[i].end = edges[j].end; edges[j].end = temp; temp = edges[i].weight; edges[i].weight = edges[j].weight; edges[j].weight = temp; } void MiniSpanTree(MGraph *G)//生成最小生成树 { int i, j, n, m,Mincost=0; int k = 1; int parent[M]; edge edges[M]; for ( i = 1; i < G->vexnum; i++) { for (j = i + 1; j <= G->vexnum; j++) { if (G->arc[i][j].adj == 1) { edges[k].begin = i;

-7-

edges[k].end = j; edges[k].weight = G->arc[i][j].weight; k++; } } } sort(edges, G); for (i = 1; i <= G->arcnum; i++) { parent[i] = 0; } printf("最小生成树为:\n"); for (i = 1; i <= G->arcnum; i++)//核心部分 { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) { parent[n] = m; printf("< %d, %d > %d\n", edges[i].begin, edges[i].end, edges[i].weight); Mincost+=edges[i].weight; } } printf("使各城市间能够通信的最小费用为:Mincost=%d\n",Mincost); } int Find(int *parent, int f) { while ( parent[f] > 0) { f = parent[f]; } return f; }

void main()//主函数 { MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); CreatGraph(G); MiniSpanTree(G); }

-8-

2.程序运行结果:

-9-


赞助商链接

更多相关文章:
最小生成树Kruskal算法实验报告
大连民族学院 计算机科学与工程学院实验报告 实验题目: 最小生成树Kruskal 算法 课程名称: 离散数学 实验类型:□演示性 □验证性 □操作性 ■设计性 □综合性...
kruskal算法最小生成树
kruskal算法最小生成树_计算机软件及应用_IT/计算机_专业资料。kruskal 算法最小生成树 课题:用 kruskal 算法最小生成树。 编译工具:Visual Studio 2017 ...
最小生成树Kruskal算法报告
("***欢迎进入最小生成树 Kruskal 算法***\n\n"); do { switch(menu()) { case 1:creat(&ga);break; case 2:find(&ga);break; case 3:choice...
经典最小生成树prim与kruskal算法分析比较
经典最小生成树prim与kruskal算法分析比较_计算机软件及应用_IT/计算机_专业资料。经典最小生成树 prim 与 kruskal 算法分析比较 例题 农民约翰被选为他们镇的镇长!...
数学建模-最小生成树-kruskal算法及各种代码
数学建模-最小生成树-kruskal算法及各种代码_数学_自然科学_专业资料。数学建模-最小生成树-kruskal算法及各种代码含伪代码、c代码、matlab、pascal等代码 ...
最小生成树kruskal算法
最小生成树kruskal算法_工学_高等教育_教育专区。哈工大软设,c++实现最小生成树kruskal算法 /*最小生成树 kruskal 算法*/ #include<iostream> #define maxn 20...
用prim算法和Kruskal算法最小生成树
用prim算法和Kruskal算法最小生成树_计算机软件及应用_IT/计算机_专业资料。用 prim 算法和 Kruskal 算法最小生成树 2013-10-15 星期二 一、 问题表述分别用...
kruskal算法最小生成树
kruskal算法最小生成树 - #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> u...
数据结构课程设计报告最小生成树Kruskal算法[1]4545
17 I 1 1.1 课程设计内容 课程设计介绍 编写算法能够建立带权图,并能够用 Kruskal 算法求该图的 最小生成树最小生成树能够选择图上的任意一点做根结点。...
最小生成树Kruskal算法
17 关键部分程序清单) I 1 课程设计介绍 1.1 课程设计内容编写算法能够建立带权图,并能够用 Kruskal 算法求该图的 最小生成树最小生成树能够选择图上的...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图