最小生成树_kruskal与prim

时间:2020-12-29 12:34:45

首先这两种算法都是基于贪心算法,在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


最小生成树_kruskal与prim

最小生成树_kruskal与prim

对于prim算法

可以从任意根顶点开始

最小生成树_kruskal与prim最小生成树_kruskal与prim