搜索
评分签名日期湖南商学院课程设计设计名称PRIM算法最小生成树求解课程名称算法导论学期2010-2011学年第1学期学时学分51学时3学分专业班级信科0821组员名单熊春辉周伟佳刘志超学号080320637080320638080320625指导老师王勇提交日期2010年11月27日PRIM算法最小生成树求解一．问题描述：在科技发展的年代，许多问题都需要找到最简洁，最经济的方法去加以实现。假设在n个城市之间建立通信联络网，则联通n个城市只需要n-1条线路，这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。对于n个顶点的连通网可以建立许多不同的生成树，每一颗生成树都可以是一个连通网。现在，我们要选择这样一颗生成树，也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树的问题。可以推广到任意一个图的最小生成树问题。我们通过学习与阅读发现了PRIM算法有其解决这样问题的优越性。二．算法设计与分析：1.算法设计：构造最小生成树可以有多种算法。其中多数算法利用了最小生成树的下列一种简称为MST的性质：假设N=（V，{E}）是一个连通图，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值的边，其中u包含于U,v包含于V-U，则必存在一颗包含边（u,v）的最小生成树。更具体地说，我们维持一个集合S包含于V，在它上面已构造了到这步为止的生成树，初始,S={s}。每次迭代我们在S中增加一个结点，把结点v加入S能使“附加费用”min(e)=(u,v):u属于S，C（e）达到最小，并且包含了在生成树中达到这个最小值的边e=（u,v）.这样解决此问题。2.算法描述：从U={u0}u0属于V,S={}开始，重复执行下述步骤：在所有u属于U，v属于V-U的边（u,v)属于E中找一条代价最小的边（u0,v0)并入集合S，同时v0并入U，直到U=V为止，此时S中必有n-1条边，则T=(V,{S})为G的最小生成树（3）结束3.算法分析：普利姆算法算法是前人的劳动成果，是正确的，对于同一个图而言，普利姆算法的时间复杂度)(2nO，n为顶点数。三．程序设计1．程序设计的基本思路：。构造图函数，初始状态各个顶点都是独立的，根据PRIM算法，将权排序，选择权最小的边，知道所有的顶点以n-1条边连接即结束，生成最小生成树。2．程序内部实现的说明。本程序采用嵌套及其循环调用的方法实现最小生成树。采用调用PRIM算法函数voidprim()。申请内存构造函数最小生成树生成最后的结点排序函数图形初始化流程图：如下图所示步骤：权值分别为1,2,3,4,5的5条边由于满足上述条件依次输出，最后生成树如图b所示。（a）（b）四．测试结果及分析1．测试报告：特殊实例1：输入顶点数，边数，各条路径权值输出边路径特殊实例2：输入顶点数，边数，各条路径权值输出边路径实例3：输入顶点数，边数，各条路径权值输出边路径2．分析总结：因此用PRIM算法求出了最小生成树，及其的解。附录：#includestdio.h#includelimits.h#defineN100intp[N],key[N],tb[N][N];voidprim(intv,intn){inti,j;intmin;for(i=1;i=n;i++){p[i]=v;key[i]=tb[v][i];}key[v]=0;for(i=2;i=n;i++){min=INT_MAX;for(j=1;j=n;j++)if(key[j]0&&key[j]min){v=j;min=key[j];}printf(%d%d,p[v],v);key[v]=0;for(j=1;j=n;j++)if(tb[v][j]key[j])p[j]=v,key[j]=tb[v][j];}}intmain(){intn,m;inti,j;intu,v,w;while(scanf(%d%d,&n,&m)){for(i=1;i=n;i++){for(j=1;j=n;j++)tb[i][j]=INT_MAX;}while(m--){scanf(%d%d%d,&u,&v,&w);tb[u][v]=tb[v][u]=w;}prim(1,n);printf(\n);}return0;}课程设计成绩评定表等级成绩组成优秀良好中等及格不及格报告文档1．文档很规范。2．排版很清晰。3．内容很全面。4．设计很合理。1．文档规范。2．排版清晰。3．内容全面。4．设计合理。1．文档较规范。2．排版较清晰。3．内容较全面。4．设计较合理。1．文档欠规范。2．排版欠清晰。3．内容欠全面。4．设计欠合理。1．文档不规范。2．排版不清晰。3．内容不全面。4．设计不合理。算法分析1．算法正确。2．算法分析很全面。3．算法描述很清晰。1．算法正确。2．算法分析全面。3．算法描述清晰。1．算法正确。2．算法分析较全面。3．算法描述较清晰。1．算法基本正确。2．算法分析欠全面。3．算法描述欠清晰。1．算法不正确。2．算法分析不全面。3．算法描述不清晰。程序设计1．程序设计思路很清晰。2．程序实现要点描述很清楚。3．程序使用方式描述很清楚。1．程序设计思路清晰。2．程序实现要点描述清楚。3．程序使用方式描述清楚。1．程序设计思路较清晰。2．程序实现要点描述较清楚。3．程序使用方式描述较清楚。1．程序设计思路欠清晰。2．程序实现要点描述欠清楚。3．程序使用方式描述欠清楚。1．程序设计思路不清晰。2．程序实现要点描述不清楚。3．程序使用方式描述不清楚。结果分析1．有运行结果描述。2．结果描述很清晰、很完整。3．结果分析很深入。1．有运行结果描述。2．结果描述清晰、完整。3．结果分析深入。1．有运行结果描述。2．结果描述较清晰、较完整。3．结果分析较深入。1．有运行结果描述。2．结果描述欠清晰、欠完整。3．结果分析欠深入。1．无运行结果描述。2．结果描述不清晰、很完整。3．结果分析不深入。代码编写1．程序运行正确。2．程序代码编写很整洁规范。3．程序代码内有详细的注释。1．程序运行正确。2．程序代码编写整洁规范。3．程序代码内有较多的注释。1．程序运行正确。2．程序代码编写较整洁规范。3．程序代码内有一些基本的注释。1．程序运行基本正确。2．程序代码编写欠整洁规范。3．程序代码内有较少的注释。1．程序运行不正确。2．程序代码编写不整洁规范。3．程序代码内没有注释。综合成绩评定：评阅老师（签章）：年月日