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

【文章來源】：遼寧大學(xué)學(xué)報(自然科學(xué)版). 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 算法選擇與應(yīng)用
    2.1 算法選擇
    2.2 程序設(shè)計實例
        2.2.1 基本最小生成樹問題
        2.2.2 需要優(yōu)化的最小生成樹問題
        2.2.3 最小生成樹中最大邊問題
        2.2.4 求擴充邊的最小權(quán)值和問題
        2.2.5 刪點后的最小生樹問題
        2.2.6 最小生成樹唯一性問題
3 結(jié)論


【參考文獻(xiàn)】：
期刊論文
[1]Kruskal和Prim算法的分析研究與比較[J]. 賀軍忠,王麗君.  隴東學(xué)院學(xué)報. 2020(02)
[2]應(yīng)用Kruskal的改進(jìn)算法求最小生成樹[J]. 袁威威.  江蘇第二師范學(xué)院學(xué)報. 2017(06)



本文編號：3204230