贪心算法实现最小生成树
Prim算法 设G=(V,E)是连通带权图,V={1,2,…,n}。构造G的最小生成树的Prim算法的基本思想是: (1)置S={1} (2)只要S是V的真子集,就作如下的贪心选择 选取满足条件i ∈ S,j ∈ V-S,且c[j]最小的边,将顶点j添加到S中。一直到S=V时为止。 (3)选取到的所有边恰好构成G的一棵最小生成树。
用户评论
qq588914257 2018-12-07 14:32:39
很远很好,解释也清楚。图论是我心中永远的痛,唉。