應用最小生成樹構造最優通信網

宋海燕

摘 要：信息社會中，通信網絡建設在快速發展，建設費用昂貴，如何使建設線路最短，從而降低建設成本成為國家關注的重點。該文針對建設路徑最短的問題，應用數據結構中的最小生成樹理論引入了與最小生成樹相關的基本概念與定理，分析了通信網絡線路與最小生成樹的關系，最后，應用最小生成樹算法解決了通信網絡線路最短的實際問題。

關鍵詞：最小生成樹 最優通信網 Prim算法 Kruscal算法

中圖分類號：TP393.02 文獻標識碼：A 文章編號：1674-098X（2014）11（c）-0028-01

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

3.1 算法思想

（1）將圖各邊按照權值從小到大排序。

（2）依次選入權值最小的邊（條件：此次找出的邊不能和已加入最小生成樹集合的邊構成環），若符合條件，則加入最小生成樹的集合中；若不符合條件則按次序選擇下一條最小權值的邊。直到找出n-1條邊為止（設圖有n個結點，則最小生成樹的邊數應為n-1條），算法結束，得到的就是此圖的最小生成樹。

3.2 構造過程

六個頂點五條邊即可以連通，應用Kruscal算法構造的最小生成樹。

4 結語

應用Prim算法和Kruscal算法構造的連通網的最小生成樹，就是最優通信網，它既可以實現各個城市連通，又可以保證通信線路最短，是降低通信網絡建設成本的有效途徑。

參考文獻

[1] 謝柏青，余曉歌.算法與數據結構[M].高等教育出版社，2001.

[2] 劉自昆.數據結構[M].西南師范大學出版社，2006.

[3] 李筠，姜學軍.數據結構[M].清華大學出版社，2005.endprint

摘 要：信息社會中，通信網絡建設在快速發展，建設費用昂貴，如何使建設線路最短，從而降低建設成本成為國家關注的重點。該文針對建設路徑最短的問題，應用數據結構中的最小生成樹理論引入了與最小生成樹相關的基本概念與定理，分析了通信網絡線路與最小生成樹的關系，最后，應用最小生成樹算法解決了通信網絡線路最短的實際問題。

關鍵詞：最小生成樹 最優通信網 Prim算法 Kruscal算法

中圖分類號：TP393.02 文獻標識碼：A 文章編號：1674-098X（2014）11（c）-0028-01

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

3.1 算法思想

（1）將圖各邊按照權值從小到大排序。

（2）依次選入權值最小的邊（條件：此次找出的邊不能和已加入最小生成樹集合的邊構成環），若符合條件，則加入最小生成樹的集合中；若不符合條件則按次序選擇下一條最小權值的邊。直到找出n-1條邊為止（設圖有n個結點，則最小生成樹的邊數應為n-1條），算法結束，得到的就是此圖的最小生成樹。

3.2 構造過程

六個頂點五條邊即可以連通，應用Kruscal算法構造的最小生成樹。

4 結語

應用Prim算法和Kruscal算法構造的連通網的最小生成樹，就是最優通信網，它既可以實現各個城市連通，又可以保證通信線路最短，是降低通信網絡建設成本的有效途徑。

參考文獻

[1] 謝柏青，余曉歌.算法與數據結構[M].高等教育出版社，2001.

[2] 劉自昆.數據結構[M].西南師范大學出版社，2006.

[3] 李筠，姜學軍.數據結構[M].清華大學出版社，2005.endprint

摘 要：信息社會中，通信網絡建設在快速發展，建設費用昂貴，如何使建設線路最短，從而降低建設成本成為國家關注的重點。該文針對建設路徑最短的問題，應用數據結構中的最小生成樹理論引入了與最小生成樹相關的基本概念與定理，分析了通信網絡線路與最小生成樹的關系，最后，應用最小生成樹算法解決了通信網絡線路最短的實際問題。

關鍵詞：最小生成樹 最優通信網 Prim算法 Kruscal算法

中圖分類號：TP393.02 文獻標識碼：A 文章編號：1674-098X（2014）11（c）-0028-01

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

3.1 算法思想

（1）將圖各邊按照權值從小到大排序。

（2）依次選入權值最小的邊（條件：此次找出的邊不能和已加入最小生成樹集合的邊構成環），若符合條件，則加入最小生成樹的集合中；若不符合條件則按次序選擇下一條最小權值的邊。直到找出n-1條邊為止（設圖有n個結點，則最小生成樹的邊數應為n-1條），算法結束，得到的就是此圖的最小生成樹。

3.2 構造過程

六個頂點五條邊即可以連通，應用Kruscal算法構造的最小生成樹。

4 結語

應用Prim算法和Kruscal算法構造的連通網的最小生成樹，就是最優通信網，它既可以實現各個城市連通，又可以保證通信線路最短，是降低通信網絡建設成本的有效途徑。

參考文獻

[1] 謝柏青，余曉歌.算法與數據結構[M].高等教育出版社，2001.

[2] 劉自昆.數據結構[M].西南師范大學出版社，2006.

[3] 李筠，姜學軍.數據結構[M].清華大學出版社，2005.endprint