最小生成樹：貪心算法的經典應用，Prim算法入門
本文介紹了生成樹、最小生成樹（MST）及Prim算法。生成樹是連通無向圖的無環子圖，含所有頂點；MST是邊權和最小的生成樹，適合貪心算法（每步選局部最優得全局最優）。 Prim算法核心步驟：選起點，反覆從已選和未選頂點間的邊中選最小權邊，將對應頂點加入已選集，直至所有頂點入集。關鍵是用鄰接矩陣或鄰接表記錄圖結構，算法僞代碼中，`key`數組記錄最小邊權，`parent`記錄父節點，時間複雜度鄰接矩陣爲O(n²)，優化後O(m log n)。 Prim算法基於貪心選擇，安全邊性質保證總權最小，應用於網絡佈線、電路設計等需最小成本連接所有節點的場景。總結：MST是貪心算法經典應用，Prim通過逐步擴展選最小邊高效構建最優生成樹。
閱讀全文貪心算法：貪心算法是什麼？找零錢問題實例講解
貪心算法是每步選擇當前最優（局部最優）以期望全局最優的算法，核心是滿足“貪心選擇性質”——每步局部最優能導致全局最優。經典應用如找零錢：以25、10、5、1分硬幣爲例，找67分時，按從大到小逐步取25×2（50分）、10×1（10分）、5×1（5分）、1×2（2分），共6枚，驗證爲最優。其侷限性在於，若問題不滿足貪心選擇性質（如硬幣面額[1,3,4]找6分），貪心可能失效（貪心取4+1+1=3枚，最優爲3+3=2枚）。適用場景包括硬幣面額合理（如25、10、5、1）、活動安排（選最早結束活動）等。總之，貪心算法簡單直觀高效，但僅適用於滿足貪心選擇性質的問題，不保證所有問題全局最優。
閱讀全文