文件名称:贪心算法实现最小生成树
文件大小: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的一棵最小生成树。