应用最小生成树构造最优通信网

宋海燕

摘 要：信息社会中，通信网络建设在快速发展，建设费用昂贵，如何使建设线路最短，从而降低建设成本成为国家关注的重点。该文针对建设路径最短的问题，应用数据结构中的最小生成树理论引入了与最小生成树相关的基本概念与定理，分析了通信网络线路与最小生成树的关系，最后，应用最小生成树算法解决了通信网络线路最短的实际问题。

关键词：最小生成树 最优通信网 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