两类网络连接问题中的最小费用算法及其应用  

Minimum Cost Algorithm and Its Application in Two Types of Network Connection

作　　者：方冬云[1] 

机构地区：[1]莆田学院数学与应用数学系,福建莆田351100

出　　处：《四川理工学院学报（自然科学版）》2009年第6期16-18,共3页Journal of Sichuan University of Science & Engineering(Natural Science Edition)

基　　金：福建省自然科学高校专项资助项目(A0540011)

摘　　要：利用MergeSort算法对加权图中任意两点之间的权值进行排序,把这些权值从小到大进行排列放在一个队列,再利用Kruskal算法求该队列的最小生成树,并将该方法运用于城市交通网络的费用计算;而对于供水管道铺设的最小费用问题可通过最小树形图算法来解决。Using the MergeSort algorithm, weights between any two points in weighted graph is ordered in this paper. Firstly, the weights from small to large in a quene is ranked. Then by using Kruskal algorithm for seeking the minimum spanning tree in this queue, we can apply this method to work out the cost of Urban transportation network. It can be solved by minimal tree algorithm to minimize cost of laying water supply pipes.

关 键 词：MergeSort算法 KRUSKAL算法 最小树形图算法 网络连接 

分 类 号：O157.5[理学—数学]