| 附有条件的最小支撑树算法 |
| |
| 引用本文： | 厍向阳,罗晓霞. 附有条件的最小支撑树算法[J]. 西安科技大学学报, 2008, 28(4) |
| |
| 作者姓名： | 厍向阳 罗晓霞 |
| |
| 作者单位： | 西安科技大学计算机科学与技术学院,陕西,西安,710054 |
| |
| 基金项目： | 国家自然科学基金资助项目 ， 陕西省教育厅专项科研计划项目 |
| |
| 摘 要： | 传统最小生成树算法不能解决:度约束条件下的最小支撑树问题;动态网络的最小支撑树问题;边约束条件下的最小支撑树问题。遗传算法可以求解度约束条件下的最小支撑树问题,但存在效率低、编码复杂等缺陷。归纳了3类附有条件的最小支撑树数学模型,在最小支撑树传统算法基础上,提出了3类附有条件的最小支撑树算法。算法测试和比较表明:附有条件的最小支撑树算法是完全可行和有效的。
|
| 关 键 词： | 最小支撑树 邻接矩阵 度约束 边约束 |
Minimum spanning tree algorithm confined in conditions |
| |
| SHE Xiang-yang,LUO Xiao-xia. Minimum spanning tree algorithm confined in conditions[J]. JOurnal of XI’an University of Science and Technology, 2008, 28(4) |
| |
| Authors: | SHE Xiang-yang LUO Xiao-xia |
| |
| Abstract: | The traditional algorithm of minimum spanning tree algorithm is invalidation facing the minimum spanning tree question confined in degree,the minimum spanning tree question in dynamic condition and the minimum spanning tree question confined in edge set,in practice.Genetic algorithm can solve the minimum spanning tree confined in degree,but it take on poor efficiency and complex coding.The models of the minimum spanning tree algorithm confined in conditions are generated.The three minimum spanning tree algorithms confined in conditions is put forward based on traditional algorithm.The algorithms are validated and compared,and show the minimum spanning tree algorithm confined in conditions is completely feasible and effective. |
| |
| Keywords: | minimum spanning tree adjacency matrix degree confining edge set confining |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
