應(yīng)用最小生成樹(shù)構(gòu)造最優(yōu)通信網(wǎng)

宋海燕

摘 要：信息社會(huì)中，通信網(wǎng)絡(luò)建設(shè)在快速發(fā)展，建設(shè)費(fèi)用昂貴，如何使建設(shè)線路最短，從而降低建設(shè)成本成為國(guó)家關(guān)注的重點(diǎn)。該文針對(duì)建設(shè)路徑最短的問(wèn)題，應(yīng)用數(shù)據(jù)結(jié)構(gòu)中的最小生成樹(shù)理論引入了與最小生成樹(shù)相關(guān)的基本概念與定理，分析了通信網(wǎng)絡(luò)線路與最小生成樹(shù)的關(guān)系，最后，應(yīng)用最小生成樹(shù)算法解決了通信網(wǎng)絡(luò)線路最短的實(shí)際問(wèn)題。

關(guān)鍵詞：最小生成樹(shù) 最優(yōu)通信網(wǎng) Prim算法 Kruscal算法

中圖分類(lèi)號(hào)：TP393.02 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）11（c）-0028-01

隨著現(xiàn)代科技的飛速發(fā)展，通信技術(shù)也得到迅猛的發(fā)展，中國(guó)的通信產(chǎn)業(yè)高速運(yùn)行，通信市場(chǎng)競(jìng)爭(zhēng)加大。在信息時(shí)代，各通信公司為了爭(zhēng)占市場(chǎng)，紛紛加大對(duì)通信網(wǎng)絡(luò)的建設(shè)工作，但是高昂的建設(shè)費(fèi)用使通信公司承擔(dān)了巨大的經(jīng)濟(jì)壓力，如何降低通信網(wǎng)絡(luò)的建設(shè)成本是保證運(yùn)營(yíng)商贏得市場(chǎng)的關(guān)鍵。優(yōu)化通信網(wǎng)絡(luò)建設(shè)線路是降低建設(shè)費(fèi)用的一個(gè)途徑，如圖1所示，假設(shè)A，B，C，D，E，F(xiàn)代表六個(gè)城市，任意兩個(gè)城市間連線上的數(shù)字表示兩個(gè)城市的距離，如AB兩城市間的距離為6000 km，現(xiàn)想在這六個(gè)城市間鋪設(shè)網(wǎng)絡(luò)線纜，既可以使六個(gè)城市之間連通，又能夠保證網(wǎng)絡(luò)線纜最短。該文應(yīng)用圖論中的最小生成樹(shù)理論以及生成最小生成樹(shù)的Prim算法和Kruscal算法，優(yōu)化網(wǎng)絡(luò)線路，降低建設(shè)成本。

3.1 算法思想

（1）將圖各邊按照權(quán)值從小到大排序。

（2）依次選入權(quán)值最小的邊（條件：此次找出的邊不能和已加入最小生成樹(shù)集合的邊構(gòu)成環(huán)），若符合條件，則加入最小生成樹(shù)的集合中；若不符合條件則按次序選擇下一條最小權(quán)值的邊。直到找出n-1條邊為止（設(shè)圖有n個(gè)結(jié)點(diǎn)，則最小生成樹(shù)的邊數(shù)應(yīng)為n-1條），算法結(jié)束，得到的就是此圖的最小生成樹(shù)。

3.2 構(gòu)造過(guò)程

六個(gè)頂點(diǎn)五條邊即可以連通，應(yīng)用Kruscal算法構(gòu)造的最小生成樹(shù)。

4 結(jié)語(yǔ)

應(yīng)用Prim算法和Kruscal算法構(gòu)造的連通網(wǎng)的最小生成樹(shù)，就是最優(yōu)通信網(wǎng)，它既可以實(shí)現(xiàn)各個(gè)城市連通，又可以保證通信線路最短，是降低通信網(wǎng)絡(luò)建設(shè)成本的有效途徑。

參考文獻(xiàn)

[1] 謝柏青，余曉歌.算法與數(shù)據(jù)結(jié)構(gòu)[M].高等教育出版社，2001.

[2] 劉自昆.數(shù)據(jù)結(jié)構(gòu)[M].西南師范大學(xué)出版社，2006.

[3] 李筠，姜學(xué)軍.數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，2005.endprint

摘 要：信息社會(huì)中，通信網(wǎng)絡(luò)建設(shè)在快速發(fā)展，建設(shè)費(fèi)用昂貴，如何使建設(shè)線路最短，從而降低建設(shè)成本成為國(guó)家關(guān)注的重點(diǎn)。該文針對(duì)建設(shè)路徑最短的問(wèn)題，應(yīng)用數(shù)據(jù)結(jié)構(gòu)中的最小生成樹(shù)理論引入了與最小生成樹(shù)相關(guān)的基本概念與定理，分析了通信網(wǎng)絡(luò)線路與最小生成樹(shù)的關(guān)系，最后，應(yīng)用最小生成樹(shù)算法解決了通信網(wǎng)絡(luò)線路最短的實(shí)際問(wèn)題。

關(guān)鍵詞：最小生成樹(shù) 最優(yōu)通信網(wǎng) Prim算法 Kruscal算法

中圖分類(lèi)號(hào)：TP393.02 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）11（c）-0028-01

隨著現(xiàn)代科技的飛速發(fā)展，通信技術(shù)也得到迅猛的發(fā)展，中國(guó)的通信產(chǎn)業(yè)高速運(yùn)行，通信市場(chǎng)競(jìng)爭(zhēng)加大。在信息時(shí)代，各通信公司為了爭(zhēng)占市場(chǎng)，紛紛加大對(duì)通信網(wǎng)絡(luò)的建設(shè)工作，但是高昂的建設(shè)費(fèi)用使通信公司承擔(dān)了巨大的經(jīng)濟(jì)壓力，如何降低通信網(wǎng)絡(luò)的建設(shè)成本是保證運(yùn)營(yíng)商贏得市場(chǎng)的關(guān)鍵。優(yōu)化通信網(wǎng)絡(luò)建設(shè)線路是降低建設(shè)費(fèi)用的一個(gè)途徑，如圖1所示，假設(shè)A，B，C，D，E，F(xiàn)代表六個(gè)城市，任意兩個(gè)城市間連線上的數(shù)字表示兩個(gè)城市的距離，如AB兩城市間的距離為6000 km，現(xiàn)想在這六個(gè)城市間鋪設(shè)網(wǎng)絡(luò)線纜，既可以使六個(gè)城市之間連通，又能夠保證網(wǎng)絡(luò)線纜最短。該文應(yīng)用圖論中的最小生成樹(shù)理論以及生成最小生成樹(shù)的Prim算法和Kruscal算法，優(yōu)化網(wǎng)絡(luò)線路，降低建設(shè)成本。

3.1 算法思想

（1）將圖各邊按照權(quán)值從小到大排序。

（2）依次選入權(quán)值最小的邊（條件：此次找出的邊不能和已加入最小生成樹(shù)集合的邊構(gòu)成環(huán)），若符合條件，則加入最小生成樹(shù)的集合中；若不符合條件則按次序選擇下一條最小權(quán)值的邊。直到找出n-1條邊為止（設(shè)圖有n個(gè)結(jié)點(diǎn)，則最小生成樹(shù)的邊數(shù)應(yīng)為n-1條），算法結(jié)束，得到的就是此圖的最小生成樹(shù)。

3.2 構(gòu)造過(guò)程

六個(gè)頂點(diǎn)五條邊即可以連通，應(yīng)用Kruscal算法構(gòu)造的最小生成樹(shù)。

4 結(jié)語(yǔ)

應(yīng)用Prim算法和Kruscal算法構(gòu)造的連通網(wǎng)的最小生成樹(shù)，就是最優(yōu)通信網(wǎng)，它既可以實(shí)現(xiàn)各個(gè)城市連通，又可以保證通信線路最短，是降低通信網(wǎng)絡(luò)建設(shè)成本的有效途徑。

參考文獻(xiàn)

[1] 謝柏青，余曉歌.算法與數(shù)據(jù)結(jié)構(gòu)[M].高等教育出版社，2001.

[2] 劉自昆.數(shù)據(jù)結(jié)構(gòu)[M].西南師范大學(xué)出版社，2006.

[3] 李筠，姜學(xué)軍.數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，2005.endprint

摘 要：信息社會(huì)中，通信網(wǎng)絡(luò)建設(shè)在快速發(fā)展，建設(shè)費(fèi)用昂貴，如何使建設(shè)線路最短，從而降低建設(shè)成本成為國(guó)家關(guān)注的重點(diǎn)。該文針對(duì)建設(shè)路徑最短的問(wèn)題，應(yīng)用數(shù)據(jù)結(jié)構(gòu)中的最小生成樹(shù)理論引入了與最小生成樹(shù)相關(guān)的基本概念與定理，分析了通信網(wǎng)絡(luò)線路與最小生成樹(shù)的關(guān)系，最后，應(yīng)用最小生成樹(shù)算法解決了通信網(wǎng)絡(luò)線路最短的實(shí)際問(wèn)題。

關(guān)鍵詞：最小生成樹(shù) 最優(yōu)通信網(wǎng) Prim算法 Kruscal算法

中圖分類(lèi)號(hào)：TP393.02 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）11（c）-0028-01

隨著現(xiàn)代科技的飛速發(fā)展，通信技術(shù)也得到迅猛的發(fā)展，中國(guó)的通信產(chǎn)業(yè)高速運(yùn)行，通信市場(chǎng)競(jìng)爭(zhēng)加大。在信息時(shí)代，各通信公司為了爭(zhēng)占市場(chǎng)，紛紛加大對(duì)通信網(wǎng)絡(luò)的建設(shè)工作，但是高昂的建設(shè)費(fèi)用使通信公司承擔(dān)了巨大的經(jīng)濟(jì)壓力，如何降低通信網(wǎng)絡(luò)的建設(shè)成本是保證運(yùn)營(yíng)商贏得市場(chǎng)的關(guān)鍵。優(yōu)化通信網(wǎng)絡(luò)建設(shè)線路是降低建設(shè)費(fèi)用的一個(gè)途徑，如圖1所示，假設(shè)A，B，C，D，E，F(xiàn)代表六個(gè)城市，任意兩個(gè)城市間連線上的數(shù)字表示兩個(gè)城市的距離，如AB兩城市間的距離為6000 km，現(xiàn)想在這六個(gè)城市間鋪設(shè)網(wǎng)絡(luò)線纜，既可以使六個(gè)城市之間連通，又能夠保證網(wǎng)絡(luò)線纜最短。該文應(yīng)用圖論中的最小生成樹(shù)理論以及生成最小生成樹(shù)的Prim算法和Kruscal算法，優(yōu)化網(wǎng)絡(luò)線路，降低建設(shè)成本。

3.1 算法思想

（1）將圖各邊按照權(quán)值從小到大排序。

（2）依次選入權(quán)值最小的邊（條件：此次找出的邊不能和已加入最小生成樹(shù)集合的邊構(gòu)成環(huán)），若符合條件，則加入最小生成樹(shù)的集合中；若不符合條件則按次序選擇下一條最小權(quán)值的邊。直到找出n-1條邊為止（設(shè)圖有n個(gè)結(jié)點(diǎn)，則最小生成樹(shù)的邊數(shù)應(yīng)為n-1條），算法結(jié)束，得到的就是此圖的最小生成樹(shù)。

3.2 構(gòu)造過(guò)程

六個(gè)頂點(diǎn)五條邊即可以連通，應(yīng)用Kruscal算法構(gòu)造的最小生成樹(shù)。

4 結(jié)語(yǔ)

應(yīng)用Prim算法和Kruscal算法構(gòu)造的連通網(wǎng)的最小生成樹(shù)，就是最優(yōu)通信網(wǎng)，它既可以實(shí)現(xiàn)各個(gè)城市連通，又可以保證通信線路最短，是降低通信網(wǎng)絡(luò)建設(shè)成本的有效途徑。

參考文獻(xiàn)

[1] 謝柏青，余曉歌.算法與數(shù)據(jù)結(jié)構(gòu)[M].高等教育出版社，2001.

[2] 劉自昆.數(shù)據(jù)結(jié)構(gòu)[M].西南師范大學(xué)出版社，2006.

[3] 李筠，姜學(xué)軍.數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，2005.endprint