最小生成树相关算法在计算机程序设计竞赛中的研究

发布时间：2021-05-24 12:56

　　图论是计算机程序设计大赛中的重要考查知识点.最小生成树算法是解决图论相关问题的重要策略,而且在实际生活问题中也有着广泛的应用.主要介绍最小生成树的问题模型并对两种最小生成树算法:PRIM算法和KRUSKAL算法进行相关分析比较及优化,最后通过计算机程序设计题目进行相应验证. 

【文章来源】：辽宁大学学报(自然科学版). 2020,47(02)

【文章页数】：6 页

【文章目录】：
0 引言
1 最小生成树算法
    1.1 Prim算法
    1.2 Kruskal算法
    1.3 Prim与Kruskal的比较
    1.4 算法优化
        1.4.1 Prim算法的二叉堆优化
        1.4.2 Prim算法的斐波那契堆优化
        1.4.3 Kruskal算法的并查集优化
2 算法选择与应用
    2.1 算法选择
    2.2 程序设计实例
        2.2.1 基本最小生成树问题
        2.2.2 需要优化的最小生成树问题
        2.2.3 最小生成树中最大边问题
        2.2.4 求扩充边的最小权值和问题
        2.2.5 删点后的最小生树问题
        2.2.6 最小生成树唯一性问题
3 结论


【参考文献】：
期刊论文
[1]Kruskal和Prim算法的分析研究与比较[J]. 贺军忠,王丽君.  陇东学院学报. 2020(02)
[2]应用Kruskal的改进算法求最小生成树[J]. 袁威威.  江苏第二师范学院学报. 2017(06)



本文编号：3204230