Prim 算法思想：

从任意一顶点 v0 开始选择其最近顶点 v1 构成树 T1，再连接与 T1 最近顶点 v2 构成树 T2， 如此重复直到所有顶点均在所构成树中为止。
Prim 算法步骤：
T0 存放生成树的边，初值为空
输入加权图的带权邻接矩阵 C = (Cij)n×n (两点间无边相连则其大小为无穷)
为每个顶点 v 添加一属性 L(v) ：表 v 到 T0 的最小直接距离
1) T0←∅, V1={v0}, C(T0)=0
2) 对任意v ∈ V，L(v)←C(v, v0)
3) If V==V1 then stop else goto next.
4) 在 V-V1 中找点 u 使 L(u) =min{ L(v) | v ∈ (V − V1 )},记 V1 中与 u 相邻点为 w.
5) T0←T0∪{(u, w)}, C(T0) ←C(T0)+C(u, w), V1←V1∪{u}
6) 对任意v ∈ (V − V1 ) if C(v, u)<L(v) then L(v) = C(v, u) else L(v)不变。
7) Go to 3.

Kruskal算法思想：

         把n个顶点看成看成n棵分离的树（每棵树只有一个顶点），每次选取可连接两个分离树中权值最小的边把两个分离的树合成一个新的树取代原来的两个分离树，如果重复n-1步后便得到最小生成树。

Kruskal算法步骤：

T0存放生成树的边，初值为空

C(T0) 最小生成树的权，初值为0

VS 分离树顶点的集合，初值为 { {v1} {v2} … {vn} }

A B W分别为边的顶点和权值数组，由用户输入

1)         T0←0, C(T0)←0, VS←{ {v1} {v2} … {vn} }, A, B, W按W排序后构成队列Q

2)         If n(VS)==1 then stop else goto 3

3)         取Q第一组数组(u, v, w) 并从Q中将其删除.

4)         If u, v 属于同一个集合 then goto 3 else 分属两个集合X, Y, goto 5.

5)         T0←T0∪(u, v), C(T0)←C(T0)+w, VS←VS-X-Y+X∪Y goto 2.

 

Kruskal算法证明：

树定义：无圈连通图。

引理1：一个图是树 等价于 一个图无圈且任意不相关联的顶点u, v ，图G+(u, v)则必存在唯一一个圈。

         设由Kruskal算法生成的T0序列为e1, e2, e3 … ev-1，假设其不是最小生成树。任意最小生成树T定义函数f(T)：T0中不存在于T中边在T0的下标。设T1是使f(T)最大的变量，设f(T1)=k，即ek不存在于T1中，T1为树且ek不在T1中，所以由引理1得T1+ek必存在圈C，C上必有e,k ≠ek，e,k不在T0 中。现令T2 = T1 - e,k + ek，则T2也为生成树但由Kruskal算法可知ek是使e1, e2 … ek-1, ek无圈的权值最小的边，e1, e2 … ek-1, e,k是树的子图必无圈故e,k的权值必定小于ek，即T2的总权值不大于T1的权值，因T1是最小生成树，故必T2也是最小生成树，但f(T2)＞k与k是f函数最大取值矛盾，故T0是最小生成树。