本站原创
【摘要】N个城市间有多种的网络建设方案，本文使用最小支撑树的原理，运用算法中的普林算法进行运算。得到的最小生成树使n个城市间的连接是连通的，而且是最经济的在各种网络建设方案中。
【关键词】最小支撑树；普林算法
Abstract：N cities he 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
1.引言
当今时怎么发表展迅速，各个城市之间需要有比较方便的通讯和联系。这就需要在各个城市间建立通信，这就涉及到了网络建设，网络建设的方案很多而且差别较大，这就需要根据当地网络建设的实际要求进行设计。本文就N个城市间的网络建设以最经济的策略进行了设计。N个城市间的最经济的网络建设就要求他们之间是一个连通的关系，各个城市间就可以进行通信，这避开了每两个城市间直接建立连接的各种建设费用，而怎样连接才能使经济成本最低呢？这就涉及到了最小支撑树，以及实现最小支撑树的算法。本文就七个城市间的通信，来解决他们之间的网络建设的最经济的连接策略。
如果要实现这七个城市间的通信，则按照两两之间建立联系的方式可以建立一个通N个城市间的最经济的网络建设由专注毕业论文与职称论文的www.udooo.com提供,转载请保留.信网络，可以保证通信的正常。但是这样也同样会带来理由，这样在两两城市之间建立通信，需要的设备和线路比较多，会使建设费用大幅度的增加，是一种不合理的建网方式。我们可以寻找一种最经济的建网的方式，既不影响网络的通信，又是建设费用大幅度的降低，这是我们所追求的。这就涉及到了最小支撑树的理由。我们可以利用最小生成树原理进行最经济的网络建设。人们总想寻找最经济的策略将一个终端集合，通过某种方式将其连接起来。如“用通讯线路把若干城市联结起来，要求设计最短通信线路”，“为了解决苦于居民点供水，要求设计最短的自来水管线路”等，总之，求最小生成树是现实世界中解决实际理由的需要参考[1]。我们可以用普林算法得到最小生成树，也就得到了最经济的建网方案和连接方式[2]。
下面是用普林算法来求最小树。
可以用普林算法来求出最小树，首先选择带最小权的边，吧它放进支撑树里，相继向树里添加带最小权的边，这些边与已在书里的边形成圈，当已经添加了n-1条边为止[3]。根据普林算法我们可以进行运算：
选择 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所示。
对于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}，
N个城市间的最经济的网络建设由提供海量免费论文范文的www.udooo.com,希望对您的论文写作有帮助.{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个城市间的最经济的网络连接可以得到实现。
4.结论
通过使用最小生成树原理，并且运用普林算法我们可以得到七个城市之间的最小生成树，通过最小生成树，这七个城市自建可以形成一个互通的网络，并且实现了最经济的组网方式，这体现了最小生成树的用法。
参考文献
[1]太原师院计算机教研室.求最小生成树的一个算法[J].太原师范专科学校学报，1999.
[2]徐俊明.图论及其应用[M].中国科技大学出版社，2000.
[3]吴文虎，等.图论的算法与程序设计[M].清华大学出版社，2002.
[4]陈莉，等.离散数学[M].高等教育出版社，2002.
作者简介：
徐刚（1974—），男，现供职于陆军航空兵学院信息技术教研室，主要从事电工电子教学工作。
魏琴（1985—），女，现供职于陆军航空兵学院信息技术教研室，主要从事电工电子教学工作。
【关键词】最小支撑树；普林算法
Abstract：N cities he 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
1.引言
当今时怎么发表展迅速，各个城市之间需要有比较方便的通讯和联系。这就需要在各个城市间建立通信，这就涉及到了网络建设，网络建设的方案很多而且差别较大，这就需要根据当地网络建设的实际要求进行设计。本文就N个城市间的网络建设以最经济的策略进行了设计。N个城市间的最经济的网络建设就要求他们之间是一个连通的关系，各个城市间就可以进行通信，这避开了每两个城市间直接建立连接的各种建设费用，而怎样连接才能使经济成本最低呢？这就涉及到了最小支撑树，以及实现最小支撑树的算法。本文就七个城市间的通信，来解决他们之间的网络建设的最经济的连接策略。
2.解决七个城市间通信的最经济的建网策略普林算法
有七个城市，要实现他们之间的通信，图1是这七个城市的具体关系：如果要实现这七个城市间的通信，则按照两两之间建立联系的方式可以建立一个通N个城市间的最经济的网络建设由专注毕业论文与职称论文的www.udooo.com提供,转载请保留.信网络，可以保证通信的正常。但是这样也同样会带来理由，这样在两两城市之间建立通信，需要的设备和线路比较多，会使建设费用大幅度的增加，是一种不合理的建网方式。我们可以寻找一种最经济的建网的方式，既不影响网络的通信，又是建设费用大幅度的降低，这是我们所追求的。这就涉及到了最小支撑树的理由。我们可以利用最小生成树原理进行最经济的网络建设。人们总想寻找最经济的策略将一个终端集合，通过某种方式将其连接起来。如“用通讯线路把若干城市联结起来，要求设计最短通信线路”，“为了解决苦于居民点供水，要求设计最短的自来水管线路”等，总之，求最小生成树是现实世界中解决实际理由的需要参考[1]。我们可以用普林算法得到最小生成树，也就得到了最经济的建网方案和连接方式[2]。
下面是用普林算法来求最小树。
可以用普林算法来求出最小树，首先选择带最小权的边，吧它放进支撑树里，相继向树里添加带最小权的边，这些边与已在书里的边形成圈，当已经添加了n-1条边为止[3]。根据普林算法我们可以进行运算：
选择 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所示。
对于n个城市之间的最经济的连接也可用普林算林算法进行设计。
3.按普林算法编写的源程序
下面是用邻接矩阵表示的图的普林算法的源程序：#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}，
N个城市间的最经济的网络建设由提供海量免费论文范文的www.udooo.com,希望对您的论文写作有帮助.{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个城市间的最经济的网络连接可以得到实现。
4.结论
通过使用最小生成树原理，并且运用普林算法我们可以得到七个城市之间的最小生成树，通过最小生成树，这七个城市自建可以形成一个互通的网络，并且实现了最经济的组网方式，这体现了最小生成树的用法。
参考文献
[1]太原师院计算机教研室.求最小生成树的一个算法[J].太原师范专科学校学报，1999.
[2]徐俊明.图论及其应用[M].中国科技大学出版社，2000.
[3]吴文虎，等.图论的算法与程序设计[M].清华大学出版社，2002.
[4]陈莉，等.离散数学[M].高等教育出版社，2002.
作者简介：
徐刚（1974—），男，现供职于陆军航空兵学院信息技术教研室，主要从事电工电子教学工作。
魏琴（1985—），女，现供职于陆军航空兵学院信息技术教研室，主要从事电工电子教学工作。