黃寧高中數學-高一數-多項式的運算(五)

最小成本生成樹 ( minimum cost spanning tree )

http://210.240.194.97/course/2007/Algorithms/poko/prim.htm

最小成本生成樹 ( minimum cost spanning tree )

在圖形中若於個邊 (edge) 上加上一些值，此數值稱為比重 ( weight ) 。而此圖形稱為比重圖形 (Weight Graph ) ，若 weight 是成本 ( cost ) 或距離( distance ) ，則稱此圖形為網路 ( Network )。根據Spanning Tree 的定義，知一個圖形可有許多不同 spanning tree ，在 network 中找出一個具有最小成本 ( Cost )的Spanning tree ，則此 Spanning tree 稱為最小成本生成樹。

Prims 演算法

有一個網路， G = (V,E) ，其中 V={0,1,2,3,…,n}，最初設定 U={0}，U,V 是個頂點集，然後從 U-V 集合中找一個頂點V，能與U集合中的某頂點形成最小成本的邊，把這一頂點V加入U集合，繼續此步驟，直到U集合等於V集合為止。

1.首先選擇0

2.選擇頂點5 因其最接近0

3.選擇頂點4 因其最接近{0，5}

4.選擇頂點3 因其最接近{0，5，4}

5.選擇頂點2 因其最接近(0，5，4，3)

6.選擇頂點1 因其最接近(0，5，4，3，2)

7.選擇頂點6 因其最接近(0，5，4，3，2，1)