求解度约束最小生成树的新的快速算法

摘要

针对度约束最小生成树问题,提出了一种新的快速算法.新的快速算法分为两个主要部分,第一部分从一棵最小生成树出发,构造一棵度约束树.第二部分设计了一种改进策略,从第一部分求得的度约束树出发,每次去掉树的一条边,将顸点按照连通性划分成两个集合,在不违反度约束的情况下,从这两个集合构成的边割中,选择一条权值减少最大的边添加到图中.通过大量的数值实验表明新的快速算法性能良好.