PRIM算法图的最小生成树求解.doc

《PRIM算法图的最小生成树求解.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、评分签名日期湖南商学院课程设计设计名称PRIM算法最小生成树求解课程名称算法导论学期2010-2011学年第1学期　学时学分51学时3学分　专业班级信科0821组员名单熊春辉周伟佳刘志超学号指导老师王勇提交日期2010年11月27日PRIM算法最小生成树求解一．问题描述：在科技发展的年代，许多问题都需要找到最简洁，最经济的方法去加以实现。假设在n个城市之间建立通信联络网，则联通n个城市只需要n-1条线路，这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。对于n个顶点的连通网可以建立许多不同的生成树，每一颗生成树都可以是一个连通网。现在，我们要选择这样一颗生成

2、树，也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树的问题。可以推广到任意一个图的最小生成树问题。我们通过学习与阅读发现了PRIM算法有其解决这样问题的优越性。二．算法设计与分析：1.算法设计：构造最小生成树可以有多种算法。其中多数算法利用了最小生成树的下列一种简称为MST的性质：假设N=（V，{E}）是一个连通图，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值的边，其中u包含于U,v包含于V-U，则必存在一颗包含边（u,v）的最小生成树。更具体地说，我们维持一个集合S包含于V，在它上面已构造了到这步为止的生成树，初始,S={s}。每次迭代我们在S中增加

3、一个结点，把结点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.算法分析：普利姆算法算法是前人的劳动成果，是正确的，对于同一个图而言，普利姆算法的时间复杂度，n为顶点数。三．程序设计1．程序设计的基本思路：。构造

4、图函数，初始状态各个顶点都是独立的，根据PRIM算法，将权排序，选择权最小的边，知道所有的顶点以n-1条边连接即结束，生成最小生成树。2．程序内部实现的说明。本程序采用嵌套及其循环调用的方法实现最小生成树。采用调用PRIM算法函数voidprim()。流程图：如下图所示步骤：权值分别为1,2,3,4,5的5条边由于满足上述条件依次输出，最后生成树如图b所示。（a）（b）四．测试结果及分析1．测试报告：特殊实例1：输入顶点数，边数，各条路径权值输出边路径特殊实例2：输入顶点数，边数，各条路径权值输出边路径实例3：输入顶点数，边数，各条路径权值输出边路径2．分析总结：因此用PRIM

5、算法求出了最小生成树，及其的解。附录：#include#include#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]

6、;for(j=1;j<=n;j++)if(tb[v][j]

7、告文档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．算法基本