最小生成樹：貪心算法的經典應用，Prim算法入門

本文介紹了生成樹、最小生成樹（MST）及Prim算法。生成樹是連通無向圖的無環子圖，含所有頂點；MST是邊權和最小的生成樹，適合貪心算法（每步選局部最優得全局最優）。 Prim算法核心步驟：選起點，反覆從已選和未選頂點間的邊中選最小權邊，將對應頂點加入已選集，直至所有頂點入集。關鍵是用鄰接矩陣或鄰接表記錄圖結構，算法僞代碼中，`key`數組記錄最小邊權，`parent`記錄父節點，時間複雜度鄰接矩陣爲O(n²)，優化後O(m log n)。 Prim算法基於貪心選擇，安全邊性質保證總權最小，應用於網絡佈線、電路設計等需最小成本連接所有節點的場景。總結：MST是貪心算法經典應用，Prim通過逐步擴展選最小邊高效構建最優生成樹。