圖論是計算機程序設計大賽中的重要考查知識點.最小生成樹算法是解決圖論相關問題的重要策略,而且在實際生活問題中也有著廣泛的應用.主要介紹最小生成樹的問題模型并對兩種最小生成樹算法:PRIM算法和KRUSKAL算法進行相關分析比較及優(yōu)化,最后通過計算機程序設計題目進行相應驗證. 

【文章來源】：遼寧大學學報(自然科學版). 2020,47(02)

【文章頁數(shù)】：6 頁

【文章目錄】：
0 引言
1 最小生成樹算法
    1.1 Prim算法
    1.2 Kruskal算法
    1.3 Prim與Kruskal的比較
    1.4 算法優(yōu)化
        1.4.1 Prim算法的二叉堆優(yōu)化
        1.4.2 Prim算法的斐波那契堆優(yōu)化
        1.4.3 Kruskal算法的并查集優(yōu)化
2 算法選擇與應用
    2.1 算法選擇
    2.2 程序設計實例
        2.2.1 基本最小生成樹問題
        2.2.2 需要優(yōu)化的最小生成樹問題
        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