最小生成树(prim算法)贪心算法.doc

离散大作业 最小生成树算法 一Prim算法 设G=(V,E)是连通带权图V={1,2,n}构造G的最小生成树的Prim算法的基本思想是 (1)置S={1} (2)只要S是V的真子集就作如下的贪心选择 选取满足条件i Sj V-S且c[i][j]最小的边将顶点j添加到S中 一直到S=V时为止 (2)选取到的所有边恰好构成G的一棵最小生成树 二源代码 #include"stdio.h" int po