數據結構之最小生成樹

最小生成樹的概念和應用背景

　　最小生成樹（Minimum Spanning Tree）各邊權的總和最小的生成樹
　　MST性質
　　假設N=(VE)是一個連通網U是頂點集V的一個非空子集若(UV)是一條具有最小權值的邊其中u∈Uv∈VU則必存在一棵包含邊(UV)的最小生成樹

構造最小生成樹的常用算法

　　普裡姆（Prim）算法
　　基本思想設G=(VE)是連通網頂點集V={vv…vn}T=(UTE)是欲構造的最小生成樹任選V中一頂點（不妨為v）初始化U={v}TE=Φ重復下列操作在所有u∈U中v∈VU的邊（uv)∈E中選擇一條權值最小的邊(uv)並入TE同時將v並入U直到U=V為止這時產生的TE中具有n條邊則上述過程求得的T=(UTE)是G的一棵最小生成樹
　　普裡姆算法的時間復雜度為O(n)與圖中邊數無關該算法適合於稠密圖
　　克魯斯卡爾（Kruskal）算法
　　基本思想設T是無向連通網G的最小生成樹E(T)是其邊集則令最小生成樹的初始狀態為n個頂點而無邊的非連通圖即E(T)為空集圖中每個頂點自成一個連通分量在E中選擇權值最小的邊若該邊依附的頂點落在T中不同的連通分量上則將此邊加入到T中否則捨去此邊而選擇下一條權值最小的邊依次類推直至T中所有頂點都在同一連通分量上為止（此時已選中n條邊）
　　克魯斯卡爾算法的時間復雜度為O(elge)時間主要取決於邊數較適合於稀疏圖

From:http://tw.wingwit.com/Article/program/sjjg/201311/23588.html