首先这两种算法都是基于贪心算法,在kruskal中,集合A是一个森林,加入集合A中的安全边总是图中连接两个不同连通分支的最小权边。而在Prim中,集合A仅形成单棵树,添加入集合A中的安全边总是连接树与一个不在树中的顶点的最小权边
MST-KRUSKAL(G,w)
A为空
for each vertex v属于V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge(u,v) 属于E,taken in nondecreasing order by weight
do if FIND_set(u)!=FIND_set(v)
then A<-A并{(u,v)}
UNION(U,V)
return A
对于prim算法
可以从任意根顶点开始