【摘要】N個城市間有多種的網(wǎng)絡(luò)建設(shè)方案，本文使用最小支撐樹的原理，運用算法中的普林算法進行運算。得到的最小生成樹使n個城市間的連接是連通的，而且是最經(jīng)濟的在各種網(wǎng)絡(luò)建設(shè)方案中。

【關(guān)鍵詞】最小支撐樹；普林算法

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

1.引言

當今時代發(fā)展迅速，各個城市之間需要有比較方便的通訊和聯(lián)系。這就需要在各個城市間建立通信，這就涉及到了網(wǎng)絡(luò)建設(shè)，網(wǎng)絡(luò)建設(shè)的方案很多而且差別較大，這就需要根據(jù)當?shù)鼐W(wǎng)絡(luò)建設(shè)的實際要求進行設(shè)計。本文就N個城市間的網(wǎng)絡(luò)建設(shè)以最經(jīng)濟的方法進行了設(shè)計。N個城市間的最經(jīng)濟的網(wǎng)絡(luò)建設(shè)就要求他們之間是一個連通的關(guān)系，各個城市間就可以進行通信，這避免了每兩個城市間直接建立連接的各種建設(shè)費用，而怎樣連接才能使經(jīng)濟成本最低呢？這就涉及到了最小支撐樹，以及實現(xiàn)最小支撐樹的算法。本文就七個城市間的通信，來解決他們之間的網(wǎng)絡(luò)建設(shè)的最經(jīng)濟的連接方法。

2.解決七個城市間通信的最經(jīng)濟的建網(wǎng)方法普林算法

有七個城市，要實現(xiàn)他們之間的通信，圖1是這七個城市的具體關(guān)系：

如果要實現(xiàn)這七個城市間的通信，則按照兩兩之間建立聯(lián)系的方式可以建立一個通信網(wǎng)絡(luò)，可以保證通信的正常。但是這樣也同樣會帶來問題，這樣在兩兩城市之間建立通信，需要的設(shè)備和線路比較多，會使建設(shè)費用大幅度的增加，是一種不合理的建網(wǎng)方式。我們可以尋找一種最經(jīng)濟的建網(wǎng)的方式，既不影響網(wǎng)絡(luò)的通信，又是建設(shè)費用大幅度的降低，這是我們所追求的。這就涉及到了最小支撐樹的問題。我們可以利用最小生成樹原理進行最經(jīng)濟的網(wǎng)絡(luò)建設(shè)。人們總想尋找最經(jīng)濟的方法將一個終端集合，通過某種方式將其連接起來。如“用通訊線路把若干城市聯(lián)結(jié)起來，要求設(shè)計最短通信線路”，“為了解決苦于居民點供水，要求設(shè)計最短的自來水管線路”等，總之，求最小生成樹是現(xiàn)實世界中解決實際問題的需要參考[1]。我們可以用普林算法得到最小生成樹，也就得到了最經(jīng)濟的建網(wǎng)方案和連接方式[2]。

下面是用普林算法來求最小樹。

可以用普林算法來求出最小樹，首先選擇帶最小權(quán)的邊，吧它放進支撐樹里，相繼向樹里添加帶最小權(quán)的邊，這些邊與已在書里的邊形成圈，當已經(jīng)添加了n-1條邊為止[3]。根據(jù)普林算法我們可以進行運算：

選擇 1 2 3 4 5 6

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

權(quán) 1 2 2 3 1 4

我們最后可以得到它的最經(jīng)濟的連接方法如圖2所示。

對于n個城市之間的最經(jīng)濟的連接也可用普林算林算法進行設(shè)計。

3.按普林算法編寫的源程序

下面是用鄰接矩陣表示的圖的普林算法的源程序：

#include

#define MAXVEX 6

typedef char VexType；

typedef float AdjType；

typedef struct {

int n； /* 圖的頂點個數(shù) */

/*VexType vexs[MAXVEX]； 頂點信息 */

AdjType arcs[MAXVEX][MAXVEX]； /* 邊信息 */

} GraphMatrix；

typedef struct{

int start_vex，stop_vex； /* 邊的起點和終點 */

AdjType weight； /* 邊的權(quán) */

} 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++） { /* 調(diào)整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īng)濟的網(wǎng)絡(luò)連接可以得到實現(xiàn)。

4.結(jié)論

通過使用最小生成樹原理，并且運用普林算法我們可以得到七個城市之間的最小生成樹，通過最小生成樹，這七個城市自建可以形成一個互通的網(wǎng)絡(luò)，并且實現(xiàn)了最經(jīng)濟的組網(wǎng)方式，這體現(xiàn)了最小生成樹的用法。

參考文獻

[1]太原師院計算機教研室.求最小生成樹的一個算法[J].太原師范?？茖W校學報，1999.

[2]徐俊明.圖論及其應(yīng)用[M].中國科技大學出版社，2000.

[3]吳文虎，等.圖論的算法與程序設(shè)計[M].清華大學出版社，2002.

[4]陳莉，等.離散數(shù)學[M].高等教育出版社，2002.

作者簡介：

徐剛（1974—），男，現(xiàn)供職于陸軍航空兵學院信息技術(shù)教研室，主要從事電工電子教學工作。

魏琴（1985—），女，現(xiàn)供職于陸軍航空兵學院信息技術(shù)教研室，主要從事電工電子教學工作。