贪心算法实现最小生成树

时间:2015-06-02 07:40:06
【文件属性】:

文件名称:贪心算法实现最小生成树

文件大小:235KB

文件格式:DOC

更新时间:2015-06-02 07:40:06

C语言,算法,最小生成树,prim算法,贪心算法

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的一棵最小生成树。


网友评论

  • 很远很好,解释也清楚。图论是我心中永远的痛,唉。