摘要
最小生成树算法是数据结构中，求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变，有时还需兼顾其它的目标，一棵最小生成树不足以解决问题，因此找出所有的最小生成树是很有必要的，在此提出一种新的寻找所有最小生成树的算法--最小差值法。无向连通图网络通过去掉连枝生成最小生成树，一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中，用连枝的权与其它树枝的权分别作差，求最小差值。由最小差值是否为零，判断原有的最小生成树能否通过换进换出边，生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中，选择符合实时情况的最小生成树方案，该方案即为网络耗费代价的最优解。
Minimum spanning tree algorithm is an important tool for network model for cost optimal solution. The problem of network connectivity is complex and changeable in real life, sometimes also need to pay attention to other targets .It is not enough to solve the problem with a minimum spanning tree. Therefore, it is necessary to find out all of the minimum spanning tree. It presents a new method of finding all of the minimum spanning tree-The minimum difference method. Undirected con-nected graph to generate the minimum spanning tree by removing the branches, the branches join a minimum spanning tree to a ring. This algorithm is , with even the branches of the right and the other branches of the ring for the poor, the minimum differ-ence in a circle .Through judgment the minimum value whether is zero ,the original judgment of minimum spanning tree can be swapped in and out of the side ,to generate the minimum spanning tree of new .The algorithm can find out all the minimum spanning tree efficiently and regularly.Among all the minimum spanning tree scheme, select the minimum spanning tree scheme that tallied with the actual situation, the scheme is the optimum solution of the network cost.
作者
肖玲玲
范海辉
XIAO Ling-ling, FAN Hai-hui （School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China; 2.Department of Electronic and Communication Engineering, Jiangxi University of Science and Technology, Ganzhou 341000,China）
出处
《电脑知识与技术》
2014年第10期6650-6658,共9页
Computer Knowledge and Technology
关键词
网络耗费代价
连通网络模型
最小生成树
算法
最小差值法
Network cost
Communication network model
minimum spanning tree
algorithm
the minimum difference meth-od
