什麼是Prim算法？
普利姆（Prim）算法是圖的最小生成樹的一種構造算法。也就是說，在包含有n個節點的連通圖中，找出只有n-1條邊包含有n個節點的連通子圖。
畫圖模擬Prim算法構造最小生成樹的過程
問題描述：
有7個城市，現在需要修路把七個村莊連通，各個城市之間的距離用邊（權值）表示。問如何修路能保證7個城市連通且總路程數最短。
連通圖
使用Prim算法構造最小生成樹過程
Prim算法思想
- 找一個頂點v開始構造最小生成樹，從頂點v的鄰接矩陣中找到權值最小的那條邊，以及對應的頂點u。將v和u加入到visit集合中
- 連接v-u。從頂點v和u這兩個頂點的鄰接矩陣中尋找權值最小的那條邊，以及對應的頂點w。將w加入到visit集合中。
- 依次類推，直到連接所有的頂點
注意：Prim算法用到了貪心算法的思想
代碼實現
此處未按照java標準來寫。（屬性私有，創建get,set方法供外部使用）
<code>package
com.algorithm.greedy.prim;public
class
MGraph
{int
verxs;char
[] data;int
[][] weight;public
MGraph
(
int
verxs) {this
.verxs=verxs; data=new
char
[verxs]; weight=new
int
[verxs][verxs]; } }/<code>
<code>package
com.algorithm.greedy.prim;import
java.util.Arrays;public
class
MinTree
{public
void
creatGraph
(MGraph graph,
int
verx,char
data[],int
[][] weight) {for
(int
i=0
;ifor(int
j=0
;j/<code>
<code>package
com.algorithm.greedy.prim;public
class
Prim
{public
static
void
main
(String[] args)
{char
[] data=new
char
[] {'A'
,'B'
,'C'
,'D'
,'E'
,'F'
,'G'
};int
verxs=data.length;int
[][] weight=new
int
[][] { {1000
,5
,7
,1000
,1000
,1000
,2
}, {5
,1000
,1000
,9
,1000
,1000
,3
}, {7
,1000
,1000
,1000
,8
,1000
,1000
}, {1000
,9
,1000
,1000
,1000
,4
,1000
}, {1000
,1000
,8
,1000
,1000
,5
,4
}, {1000
,1000
,1000
,4
,5
,1000
,6
}, {2
,3
,1000
,1000
,4
,6
,1000
}, }; MGraph graph=new
MGraph(verxs); MinTree mintree=new
MinTree(); mintree.creatGraph(graph, verxs, data, weight); mintree.showGraph(graph); mintree.prim(graph,1
); } }/<code>
運行結果展示
分享到:
