摘要
最小耗费生成树算法已很成熟,如Dijkstra's 算法,Prim’s 算法等。但在实际应用中我们常会碰到一类问题,对最小耗费生成树中每个结点的度数有所限制。这便是带有度约束bi(i=1,2,…,n)的最小耗费生成树(DCMCST)问题,在管道系统、通信、计算机网络中均会遇到这样的问题。本文提出一种分枝界限算法来产生DCMCST。
The algorithm of minimum cost opanning tree has been well-known for along time,such as Dijkstra's algorithm,Kruskal's algorithm,Prim's algorithm.Inpractical applications we ofton encounber the problem which is that the degree of eachnode in minimum cost spanning tree is consbrained.This is degree-constrained mini-mum cost spanning tree with degree-constraint bi(i=1,2,…,n).In many fields suchas plumbing,sewage,the design of electrical circuits,communication and computornetwork,this problem in finding a DCMCST often happens.In this paper the branchand bound algorithm of degree-constrained minimum cost spanning tree is generated.
出处
《计算机应用与软件》
CSCD
1989年第6期49-54,共6页
Computer Applications and Software
