图算法|Prim算法求最小生成树
01
—
一个实际问题
要在n个城市之间铺设光缆，要求有2个：
- 这 n 个城市的任意两个之间都可以通信；
- 铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此要使铺设光缆的总费用最低。
如下所示，例如，城市A和城市B间的费用为7个单位。
02
—
最小生成树
看下最小生成树的定义
在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边，而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得 w(T) 最小，则此 T 为 G 的最小生成树。
最小生成树可以用kruskal（克鲁斯卡尔）算法或 prim（普里姆）算法求出。
03
—
prim（普里姆）算法
算法描述
输入：一个加权连通图，其中顶点集合为V，边集合为E；
初始化：Vnew = {A}，其中 A 为顶点集合V中的任一节点（起始点），Enew = {},为空；
while Vnew != V：
1. 在集合E中选取权值最小的边<u, v>
其中 u 为集合 Vnew 中的元素，而 v 不在 Vnew 集合当中，并且 v∈V
2. 将 v 加入集合 Vnew 中，将 <u, v> 边加入集合 Enew 中；
输出：使用集合 Vnew 和 Enew 来描述所得到的最小生成树。
04
—
解决问题01
选择D为起始点，在可选顶点集合中选择与D相连的最小权为A，Vnew = {D, A}, Enew={DA }
在可选顶点集合中，选择与D或A相连的最小权为F，Vnew = {D,A,F}，Enew={DA, DF}
重复以上过程，直到Vnew=V，
得到的最小生成树如下：
D
/ \
A F
\
B
/
E
/ \
G C
总费用最小为39
05
—
prim-python代码实现
prim的实现代码请参考github库：
https://github.com/jackzhenguo/machine-learning/tree/master/basics
运行以上代码，产生的结果如下：
weight sum: 39
vertex:
D
A
F
B
E
C
G
edge:
(D,A)
(D,F)
(A,B)
(B,E)
(E,C)
(E,G)
与上文的结果一致