学海网

N个城市间的最经济的网络建设

N个城市间的最经济的网络建设

徐刚 魏琴

（陆军航空兵学院 信息技术教研室，北京 101123）

摘 要：n个城市间有多种的网络建设方案，本文使用最小支撑树的原理，运用算法中的普林算法进行运算。得到的最小生成树使n个城市间的连接是连通的，而且是最经济的在各种网络建设方案中。

关键字：最小支撑树、普林算法

The most economical network construction in n cities

XuGang WeiQin

(Army Aviation Institute Infirmation Technology ,Beijing 101123, China)

Abstract: N cities have a variety of network construction plan, this article USES the principle of minimum support tree, spring algorithm operation in using the algorithm. The minimum spanning tree connection is connected between the n city, and it is the most economical in various network construction scheme.

Key words: the minimum spanning. Procedure prime.

引言

当今时代发展迅速，各个城市之间需要有比较方便的通讯和联系。这就需要在各个城市间建立通信，这就涉及到了网络建设，网络建设的方案很多而且差别较大，这就需要根据当地网络建设的实际要求进行设计。本文就N个城市间的网络建设以最经济的方法进行了设计。N个城市间的最经济的网络建设就要求他们之间是一个连通的关系，各个城市间就可以进行通信，这避免了每两个城市间直接建立连接的各种建设费用，而怎样连接才能使经济成本最低呢？这就涉及到了最小支撑树，以及实现最小支撑树的两个算法。本文就七个城市间的通信，来解决他们之间的网络建设的最经济的连接方法。

正文

有七个城市，要实现他们之间的通信，图1是这七个城市的具体关系：

如果要实现这七个城市间的通信，则按照两两之间建立联系的方式可以建立一个通信网络，可以保证通信的正常。但是这样也同样会带来问题，这样在两两城市之间建立通信，需要的设备和线路比较多，会使建设费用大幅度的增加，是一种不合理的建网方式。我们可以寻找一种最经济的建网的方式，既不影响网络的通信，又是建设费用大幅度的降低，这是我们所追求的。这就涉及到了最小支撑树的问题。我们可以利用最小生成树原理进行最经济的网络建设。人们总想寻找最经济的方法将一个终端集合，通过某种方式将其连接起来。如“用通讯线路把若干城市联结起来，要求设计最短通信线路”，“为了解决苦于居民点供水，要求设计最短的自来水管线路”等，总之，求最小生成树是现实世界中解决实际问题的需要参考。我们可以用普林算法得到最小生成树，也就得到了最经济的建网方案和连接方式。

下面是用普林算法来求最小树。

可以用普林算法来求出最小树，首先选择带最小权的边，吧它放进支撑树里，相继向树里添加带最小权的边，这些边与已在书里的边形成圈，当已经添加了n-1条边为止。根据普林算法我们可以进行运算：

选择 1 2 3 4 5 6

边 a.f a.e e.g a.b b.c c.d

权 1 2 2 3 1 4

我们最后可以得到它的最经济的连接方法如图2

图1



图2

对于n个城市之间的最经济的连接也可用普林算林算法进行设计。

下面是用邻接矩阵表示的图的普林算法的源程序：

#include #define MAXVEX 6 typedef char VexType; typedef float AdjType; typedef struct { int n; /* 图的顶点个数 */ /*VexType vexs[MAXVEX]; 顶点信息 */ AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */ } GraphMatrix; typedef struct{ int start_vex, stop_vex; /* 边的起点和终点 */ AdjType weight; /* 边的权 */ } Edge; Edge mst[5]; #define MAX 1e+8 void prim(GraphMatrix * pgraph, Edge mst[]) { int i, j, min, vx, vy; float weight, minweight; Edge edge; for (i = 0; i < pgraph->n-1; i++) { mst[i].start_vex = 0; mst[i].stop_vex = i+1; mst[i].weight = pgraph->arcs[0][i+1]; } for (i = 0; i < pgraph->n-1; i++) { /* 共n-1条边 */ minweight = MAX; min = i; for (j = i; j < pgraph->n-1; j++)/* 从所有边(vx,vy)(vx∈U,vy∈V-U)中选出最短的边 */ if(mst[j].weight < minweight) { minweight = mst[j].weight; min = j; } /* mst[min]是最短的边(vx,vy)(vx∈U, vy∈V-U)，将mst[min]加入最小生成树 */ edge = mst[min]; mst[min] = mst[i]; mst[i] = edge; vx = mst[i].stop_vex; /* vx为刚加入最小生成树的顶点的下标 */ for(j = i+1; j < pgraph->n-1; j++) { /* 调整mst[i+1]到mst[n-1] */ vy=mst[j].stop_vex; weight = pgraph->arcs[vx][vy]; if (weight < mst[j].weight) { mst[j].weight = weight; mst[j].start_vex = vx; } } } } GraphMatrix graph = { 6, {{0,10,MAX,MAX,19,21}, {10,0,5,6,MAX,11}, {MAX,5,0,6,MAX,MAX}, {MAX,6,6,0,18,14}, {19,MAX,MAX,18,0,33}, {21,11,MAX,14,33,0} } }; int main(){ int i; prim(&graph,mst); for (i = 0; i < graph.n-1; i++) printf("(%d %d %.0f)\n", mst[i].start_vex, mst[i].stop_vex, mst[i].weight); return 0; }

N个城市间的最经济的网络连接可以得到实现。

结论

通过使用最小生成树原理，并且运用普林算法我们可以得到七个城市之间的最小生成树，通过最小生成树，这七个城市自建可以形成一个互通的网络，并且实现了最经济的组网方式，这体现了最小生成树的用法。

参考文献：

太原师院计算机教研室 求最小生成树的一个算法[J] 太原师范专科学校学报 1999

徐俊明 图论及其应用[M]中国科技大学出版社 2000

吴文虎等 图论的算法与程序设计[M] 清华大学出版社 2002

陈莉等 离散数学[M] 高等教育出版社 2002

作者简介：

徐刚，男，1974年生，硕士，主要从事电工电子教学，陆军航空兵学院信息技术教研室，北京市通州区台湖镇，101123， xug1974@vip.sina.com

魏琴，女，1986年生，硕士，主要从事电工电子教学, 陆军航空兵学院信息技术教研室，北京市通州区台湖镇，101123，viggieQ@163.com




N个城市间的最经济的网络建设.doc