普里姆

基本介紹

• 中文名：普里姆
• 外文名：Prim)
• 相關：普里姆(Prim)算法
• 最適合：用於稠密圖的算法

普里姆(Prim)算法

（1）算法思想

通過每次添加一個新節點加入集合，直到所有點加入停止的最小生成樹的算法

原理：每次連出該集合到其他所有點的最短邊保證生成樹的邊權總和最小

1. 首先隨便選一個點加入集合

2. 用該點的所有邊去刷新到其他點的最短路

3. 找出最短路中最短的一條連線（且該點未被加入集合）

4. 用該點去刷新到其他點的最短路

5 重複以上操作n-1次

6 最小生成樹的代價就是連線的所有邊的權值之和

7最適合用於稠密圖的算法