圖（三）——最小生成樹

什麼是最小生成樹

帶權連通圖中，總的權值之和最小的帶權生成樹為最小生成樹 。最小生成樹也稱

最小代價生成樹或最小花費生成樹；如下圖：

構造最小生成樹的基本原則：

1、隻能利用圖中的邊來構造最小生成樹；

2、隻能使用、且僅能使用圖中的n-1條邊來連接配接圖中的n個頂點；

3、不能使用圖中産生回路的邊；

普裡姆(Prim)算法

指定頂點V1，Prim算法步驟如下：

指定頂點不唯一，則最後的最小生成樹不唯一；

克魯斯卡爾(Kruskal)算法

基本思想如下：

圖示過程如下：