一、最小生成樹介紹
圖結構是一種非常重要的非線性數據結構，帶權圖的最小生成樹在工程技術，科學管理的最優解問題中有著廣泛的應用。
最小生成樹：權值和最小的生成樹
最小生成樹的性質：假設G=(V,E)是個連通圖，U是頂點V的一個非空子集。若(u,v)是一條具有最小權值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。
產生最小生成樹必須解決下邊兩個問題：
(1) 儘可能選取權值小的邊，但不能構成迴路
(2) 選取n-1條恰當的邊以連通n個頂點。
最小生成樹的算法主要有Kruskal算法和Prim算法，他們都是貪心算法的應用。
二、最小生成樹的算法
(1) Kruskal算法
過程描述：始終以邊為主導地位，先選擇權值最小的邊，總是選擇當前可用最小權值邊，並且每次判斷兩點之間是否已經間接連通，如果已經間接連通，則跳過此邊。
時間複雜度是O(n*logn)，適用於求邊稀疏連通網的最小生成樹。
(2) Prim算法
過程描述：Prim算法始終以頂點為主導，並且起始點的選擇是任意的。
從起始點到其他點選擇最小權值邊，然後以此邊兩個頂點分別再找最小權值的邊，同樣已經間接連接的邊跳過。
時間複雜度是O(n2)，適用於求邊稠密連通網的最小生成樹。
三、最小生成樹實際應用
(1) 解決礦井通風管道設計問題
(2) 幾個城市（圖1）之間怎麼修路，可以使整體上路最短？
這個問題的求解，就可以用最小生成樹（圖2），也就是幾個城市連通的最短路徑。
圖 2