数据结构课程设计求解最小生成树.doc

《数据结构课程设计求解最小生成树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计报告课程：数据结构学号：姓名：郝祥海班级：嵌入式1班教师：王群芳时间：2011-12-12计算机科学与技术系设计名称：求解最小生成树设计目的与要求：目的：要求：设计程序完成如下功能：对给定的网和起点，实现求解最小生成树的Prim算法。设计所用软件环境：MicrosoftVisualC++问题的模型化描述及求解算法的简要描述：软件组成及使用说明：程序清单：#include"stdio.h" #include"stdlib.h" #include"malloc.h" #defineMAX20 typedefstruct{ intvexs[MAX];//顶点信息集合 intarcs[MAX

2、][MAX];//各边的权值 intvexnum;//顶点数 intarcnum;//边数 }MGraph; intLocateVex(intvexs[],intv){//确定结点是否存在 intt; for(inti=0;i

3、接矩阵数据结构与算法 课程设计报告 -17-for(j=0;j

4、d",&v1,&v2,&weight); if((v1>0&&v1<=G.vexnum)&&(v2>0&&v2<=G.vexnum)) break; else printf("输入有误，不存在该顶点，请重新输入^_^"); } i=LocateVex(G.vexs,v1);//找到两个结点在邻接矩阵中的位置 j=LocateVex(G.vexs,v2); G.arcs[i][j]=weight;//边的权值 G.arcs[j][i]=G.arcs[i][j];//置(v1,v2)成(v2,v1) } printf("------------------------------------

5、-----------"); returnG; } structclosed{ intadjvex;//依附于最小权值边在顶点集合U中的顶点 intlowcost;//存储最小边的权值 }; closedclosedge[MAX]; voidMiniTree_PRIM(MGraphG,intu){ intk=u; inti,j; for(i=0;i

6、间不连通 closedge[i].lowcost=-1; else closedge[i].lowcost=G.arcs[k][i];//调整closedge数组的最小代价lowcost为边上 的权值数据结构与算法 课程设计报告 -18-} closedge[k].lowcost=0; for(i=0;i0){//求出T的下一个结点，第K结 点 k=j; break;} for(j=0;j

7、vexnum;j++) if(closedge[j].lowcost>0) if(closedge[j].lowcost%d (%d)",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost); closedge[