N個(gè)城市間的最經(jīng)濟(jì)的網(wǎng)絡(luò)建設(shè)

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

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

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.引言

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

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

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

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

下面是用普林算法來(lái)求最小樹(shù)。

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

選擇 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)濟(jì)的連接方法如圖2所示。

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

3.按普林算法編寫(xiě)的源程序

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

#include

#define MAXVEX 6

typedef char VexType；

typedef float AdjType；

typedef struct {

int n； /* 圖的頂點(diǎn)個(gè)數(shù) */

/*VexType vexs[MAXVEX]； 頂點(diǎn)信息 */

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

} GraphMatrix；

typedef struct{

int start_vex，stop_vex； /* 邊的起點(diǎn)和終點(diǎn) */

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]加入最小生成樹(shù) */

edge = mst[min]；

mst[min] = mst[i]；

mst[i] = edge；

vx = mst[i].stop_vex； /* vx為剛加入最小生成樹(shù)的頂點(diǎn)的下標(biāo) */

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個(gè)城市間的最經(jīng)濟(jì)的網(wǎng)絡(luò)連接可以得到實(shí)現(xiàn)。

4.結(jié)論

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

參考文獻(xiàn)

[1]太原師院計(jì)算機(jī)教研室.求最小生成樹(shù)的一個(gè)算法[J].太原師范?？茖W(xué)校學(xué)報(bào)，1999.

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

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

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

作者簡(jiǎn)介：

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

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