最小生成樹：貪心算法的經典應用，Prim算法入門
本文介紹了生成樹、最小生成樹（MST）及Prim算法。生成樹是連通無向圖的無環子圖，含所有頂點；MST是邊權和最小的生成樹，適合貪心算法（每步選局部最優得全局最優）。 Prim算法核心步驟：選起點，反覆從已選和未選頂點間的邊中選最小權邊，將對應頂點加入已選集，直至所有頂點入集。關鍵是用鄰接矩陣或鄰接表記錄圖結構，算法僞代碼中，`key`數組記錄最小邊權，`parent`記錄父節點，時間複雜度鄰接矩陣爲O(n²)，優化後O(m log n)。 Prim算法基於貪心選擇，安全邊性質保證總權最小，應用於網絡佈線、電路設計等需最小成本連接所有節點的場景。總結：MST是貪心算法經典應用，Prim通過逐步擴展選最小邊高效構建最優生成樹。
閱讀全文圖：圖的基本概念，鄰接表表示法初學者指南
圖由頂點（點）和邊（連接關係）組成，頂點是基本單元，邊可單向（有向圖）或雙向（無向圖），有權圖邊帶權重（如距離），無權圖僅存連接關係。鄰接表是高效表示法，解決鄰接矩陣在稀疏圖（邊遠少於頂點平方）中空間浪費問題，核心是每個頂點對應存儲直接相連頂點的列表。無向圖鄰接表如頂點0連接1、2、3，鄰接表爲[1,2,3]；有權圖可存“鄰接點+權重”元組。鄰接表空間複雜度O(V+E)（V頂點數，E邊數），適合稀疏圖，遍歷鄰接點方便，但判斷兩點是否有邊需遍歷鄰接表。掌握鄰接表爲圖遍歷、最短路徑等算法奠定基礎。
閱讀全文