数据结构与算法课程设计说明书-图的遍历和生成树求解

课程设计说明书课程名称：数据结构与算法设计题目：图的遍历和生成树求解学院：计算机科学与信息工程学院2015年6月.设计背景1.1课程设计目的通过本课程设计，加深对《数据结构与算法》课程所学知识的理解，熟练掌握和巩固基本知识和语法规范,培养调查研究、查阅技术文献、资料、手册以及编写技术文献的能力。学会编制结构清晰、风格良好的程序，从而具备利用计算机编程分析解决综合性实际问题的初步能力。1.2题目要求课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。通过课程设计，巩固和加深对图等理论知识的理解；掌握包括问题描述、系统分析、设计建模、代码实现、结果分析等的方法；提高利用计算机分析解决综合性实际问题的基本能力；锻炼个人动手能力，历练自身素质。2.设计方案2.1设计方法2.1.1问题的分析和结构的设计思路1）图的遍历和生成树求解的所有功能有：通过录入顶点个数和边数信息，采用两种图的两种存储结构：邻接矩阵、邻接表，输出邻接矩阵和邻接表；进行深度和广度优先遍历；普利姆算法和克鲁斯卡尔算法求解最小生成树；退出程序等功能。2）需要创建图的两种存储结构：邻接矩阵、邻接表。3）选择合适的算法，实现图的遍历和生成树求解的各个功能。4）选择合适的变量，来表示图的相关信息：顶点数、边数、权值和顶点信息等。5）当信息出错时，程序应给错误信息提示，使程序设计得全面周密。2.1.2图的遍历和生成树求解系统的算法思想及设计1）由于进行普利姆算法的图多为稠密图，为便于管理，采用结构体邻接矩阵存储结构。2）由于进行广度优先遍历和克鲁斯卡尔算法的图多为稀疏图，为便于管理，采用结构体邻接表存储结构。3）由于进行图的广度优先遍历时，要用到队列的相关算法，所以还要采用链队列的存储结构。4）用普利姆算法对图进行最小生成树求解时，要用到辅助数组，要采用结构体类型的存储结构。图的遍历和生成树求解的总体流程图：开始开始随机创建带权图随机创建带权图NIIf(y=’y’)输入菜单选项Y输入菜单选项邻接矩阵存储邻接表存储邻接矩阵存储邻接表存储普里姆算法输出邻接表深度优先遍历广度优先遍历输出邻接矩阵普里姆算法输出邻接表深度优先遍历广度优先遍历输出邻接矩阵输入字母输入字母YIIf(y=’n’)结束N结束2.2方法实现2.2.1创建存储结构1）建立邻接矩阵的存储结构，其中包含：顶点数vexnum、边数arcnum向量charvexs[20]、邻接矩阵AdjMatrixarcs等变量。2）建立邻接表的存储结构，其中包含：顶点数vexnum、边数arcnum、data顶点信息域、邻接表adjlistvertices[max]等变量。3）建立链队列的存储结构，其中包含：存储结点linkqueue，以及队头指针front、队尾指针rear等变量。4）建立普利姆算法的辅助数组的存储结构，其中包含：顶点adjvex、权值lowcost两个变量。2.2.2编写函数建立具体的功能实现函数，如创建无向带权图、深度优先遍历等。用邻接矩阵存储结构构建无向带权图intcreatMGraph_L(MGraph_L&G)输出邻接矩阵voidljjzprint(MGraph_LG)深度优先遍历intdfs(algraphgra,inti)普利姆算法intPRIM(intg[][max],intn)用邻接表存储结构构建无向带权图intcreatadj(algraph&gra,MGraph_LG)输出邻接表voidadjprint(algraphgra)广度优先遍历voidbfstra(algraphgra)广度优先遍历辅助队列的初始化intinitqueue(linkqueue&q)顶点入队intenqueue(linkqueue&q,inte)顶点出队intdequeue(linkqueue&q,int&e)克鲁斯卡尔算法voidkruskal(algraphgra)主函数voidmain()3.方案实施3.1采用的数据结构说明及类型的定义1．图的邻接矩阵存储结构定义如下typedefstructArccell{intadj;/*顶点关系类型。对无权图，用1(是)或无穷大(否)表示相邻否*/ /*对带权图，则为权值*/}Arccell,AdjMatrix[20][20];typedefstruct{charvexs[20];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图的当前顶点数和弧数*/}MGraph_L;2．图的邻接表存储结构定义如下typedefstructarcnode//弧结点{intadjvex;//该弧指向的顶点的位置structarcnode*nextarc;//弧尾相同的下一条弧intweight;}arcnode;typedefstructvnode//邻接链表顶点头接点{chardata;//结点信息arcnode*firstarc;//指向第一条依附该结点的弧的指针}vnode,adjlist;typedefstruct//图的定义{adjlistvertices[max];intvexnum,arcnum;}algraph;3．广度优先遍历辅助队列的存储结构定义如下typedefstructqnode{intdata;structqnode*next;}qnode,*queueptr;//结点typedefstruct{queueptrfront;//队头queueptrrear;//队尾}linkqueue;4.普利姆算法辅助数组的存储结构定义如下typedefstruct{intadjvex;intlowcost;}closedge；3.2函数功能描述及相关函数的实现1．用邻接矩阵存储结构构建无向带权图intcreatMGraph_L(MGraph_L&G)//创建图用邻接矩阵表示{charv1,v2;inti,j,w,e,f;cout<<"创建无向图"<<endl<<"请输入图G顶点和弧的个数:如(46)不包括“()”"<<endl;cin>>G.vexnum>>G.arcnum;charch[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};inta=26;intx=0; srand((unsigned)time(NULL));//随机产生顶点while(x<G.vexnum){intm=rand()%a;chartmp=ch[x];ch[x]=ch[m+26-a];ch[m+26-a]=tmp;x++;}ch[x]='\0'; cout<<"产生的"<<G.vexnum<<"个随机顶点是"<<endl; for(x=0;x<G.vexnum;x++)printf("%c\t",ch[x]); cout<<endl; for(i=0;i<G.vexnum;i++) G.vexs[i]=ch[i]; intve[max],ve1[max];//随机产生边charo='n';while(o=='n'){srand((int)time(0));for(i=0;i<2*G.arcnum;i++) { w=rand()%G.vexnum;//对G.vexnum取余 ve[i]=w;}srand((int)time(0));//产生随机权值for(i=0;i<G.arcnum;i++) { w=rand()%max;//对G.vexnum取余 ve1[i]=w;}cout<<"产生的"<<G.arcnum<<"个随机边和权值是"<<endl;for(x=0;x<2*G.arcnum;x=x+2){printf("<%d,%d>->",ve[x],ve[x+1]);e=ve[x],f=ve[x+1];printf("<%c,%c>%d\n",G.vexs[e],G.vexs[f],ve1[x/2]);}cout<<"是否满意随机生成的边?y/n"<<endl;cin>>o;if(o=='y')//判断是否满意 break;}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j)//初始化临界矩阵{G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}for(x=0;x<2*G.arcnum;x=x+2){G.arcs[ve[x]][ve[x+1]].adj=ve1[x/2];//赋权值G.arcs[ve[x+1]][ve[x]].adj=ve1[x/2];}cout<<"图G邻接矩阵创建成功！"<<endl;returnG.vexnum;}intLocateVex(MGraph_LG,charv)//返回V的位置{inti=0;for(i=0;i<G.vexnum;i++) if(v==G.vexs[i]) returni;}2．输出邻接矩阵voidljjzprint(MGraph_LG){inti,j;for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j)cout<<setw(7)<<G.arcs[i][j].adj;cout<<endl;}}3．深度优先遍历intdfs(algraphgra,inti){visited[i]=1;//按深度优先递归遍历图gra，启示顶点为i，使用访问标志数组visitedintwe;cout<<gra.vertices[i].data;for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we)){if(visited[we]==0)dfs(gra,we);}return12;}4．普利姆算法intPRIM(intg[][max],intn)//最小生成树PRIM算法{//用普利姆算法从第1个顶点出发构造网G的最小生成树，并输出各条边intlowcost[max],prevex[max];//LOWcOST[]存储当前集合U分别到剩余结点的最短路径//prevex[]存储最短路径在U中的结点inti,j,k,min;for(i=2;i<=n;i++)//n个顶点，n-1条边{lowcost[i]=g[1][i];//初始化prevex[i]=1;//顶点未加入到最小生成树中}lowcost[1]=0;//标志顶点1加入U集合for(i=2;i<=n;i++)//形成n-1条边的生成树{min=inf;k=0;for(j=2;j<=n;j++)//寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}cout<<"<"<<prevex[k]-1<<","<<k-1<<">"<<endl;lowcost[k]=0;//顶点k加入Ufor(j=2;j<=n;j++)//修改由顶点k到其他顶点边的权值if(g[k][j]<lowcost[j]){lowcost[j]=g[k][j];prevex[j]=k;}}return0;}5．用邻接表存储结构构建无向带权图intcreatadj(algraph&gra,MGraph_LG)//用邻接表存储图{inti=0,j=0;arcnode*arc,*tem,*p;for(i=0;i!=G.vexnum;++i){gra.vertices[i].data=G.vexs[i];//初始化gra.vertices[i].firstarc=NULL;}for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j){if(gra.vertices[i].firstarc==NULL){if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;gra.vertices[i].firstarc=arc; arc->weight=G.arcs[i][j].adj;arc->nextarc=NULL;p=arc;++j;while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)//邻接矩阵向临界表转化{tem=(arcnode*)malloc(sizeof(arcnode));tem->adjvex=j;gra.vertices[i].firstarc=tem; tem->weight=G.arcs[i][j].adj;tem->nextarc=arc;arc=tem;++j;}--j;}}else{if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;p->nextarc=arc;arc->nextarc=NULL;p=arc;}}}}gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;for(i=0;i!=gra.vexnum;++i){arcnode*p;cout<<i<<"";p=gra.vertices[i].firstarc;while(p!=NULL){cout<<p->adjvex<<'('<<p->weight<<')';p=p->nextarc;}cout<<endl;}cout<<"图G邻接表创建成功！"<<endl;return1;}6．输出邻接表voidadjprint(algraphgra){inti;for(i=0;i!=gra.vexnum;++i){arcnode*p;cout<<i<<"";p=gra.vertices[i].firstarc;while(p!=NULL){cout<<p->adjvex;p=p->nextarc;}cout<<endl;}}7．广度优先遍历voidbfstra(algraphgra)//广度优先遍历{//按广度优先非递归遍历图gra，使用辅助队列q和访问标志数组visitedinti,e;linkqueueq;for(i=0;i!=gra.vexnum;++i)visited[i]=0;initqueue(q);for(i=0;i!=gra.vexnum;++i)if(!visited[i]){visited[i]=1;cout<<gra.vertices[i].data;enqueue(q,i);while(!queueempty(q)){dequeue(q,e);for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we)){if(!visited[we]){visited[we]=1;cout<<gra.vertices[we].data;enqueue(q,we);}}}}}1)广度优先遍历辅助队列的初始化intinitqueue(linkqueue&q)//初始化队列{//构造一个空队列Qq.rear=(queueptr)malloc(sizeof(qnode));q.front=q.rear;if(!q.front)return0;q.front->next=NULL;return1;}}2)顶点入队intenqueue(linkqueue&q,inte)//入队{//插入元素e为q的新队尾元素queueptrp;p=(queueptr)malloc(sizeof(qnode));if(!p)return0;p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return1;}3)顶点出队intdequeue(linkqueue&q,int&e)//出队{//若队列不空，则删除q的队头元素，用e返回其值queueptrp;if(q.front==q.rear)return0;p=q.front->next;e=p->data;q.front->next=p->next;if(q.rear==p)q.rear=q.front;free(p);return1;}8．克鲁斯卡尔算法voidkruskal(algraphgra){//用克鲁斯卡尔算法构造无向带权图gra的最小生成树，输出各条边//使用辅助数组vextcout<<"2"<<endl;inti,j;int min,k;intvext[max];//辅助数组，用于判断两个点是否在同一集合里arcnode*p,*s,*L;ints1,s2;for(i=1;i<gra.vexnum;++i) vext[i]=i;//初始化辅助数组 min=inf;//min用于记录最小权值 k=1;//k表示当前构造的第几条边,初值为1while(k<gra.vexnum) { for(i=1;i<gra.vexnum;i++) { if(gra.vertices[i].firstarc!=NULL) { for(p=gra.vertices[i].firstarc;p!=NULL;p=p->nextarc) //找出最小权值的边 if(p->weight<min) { min=p->weight; s=p; j=i;}}} if(gra.vertices[j].firstarc==s) gra.vertices[j].firstarc=s->nextarc; else { for(p=gra.vertices[j].firstarc;p!=s;p=p->nextarc) L=p; L->nextarc=s->nextarc; } s1=vext[j];//分别得到两个顶点所属的集合编号 s2=vext[s->adjvex]; if(s1!=s2)//两顶点属于不同的集合，该边是最小生成树的一条边 { printf(":(%c,%c):%d\n",gra.vertices[j].data,gra.vertices[s->adjvex].data,s->weight); k++;//生成边数加1 for(i=1;i<=gra.vexnum;i++)//两个集合统一编号 if(vext[i]==s1) vext[i]=s2;} min=inf;//将min置为最大值 }}主函数main()voidmain(){system("color5f");algraphgra;MGraph_LG;printf("\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\n\n");printf("\t\t\t欢迎！\n\n");printf("\t\t\t《数据结构与算法》课程设计\n\n");printf("\t\t\t图的遍历\n\n");printf("\t\t\t计算机科学与信息工程学院\n\n");printf("\t\t\t13级软件工程\n\n");printf("\t\t\t组员姓名:刘秋珍邢金金董博渊董盼盼\n\n");printf("\t\t\t组长姓名:刘秋珍\n\n");printf("\t\t\t学号:13031210119130312102371303121010313031210104\n\t\t\t\n\n");printf("\t\t\t指导教师：郭建林\n\n");printf("\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\2\n\n");inti,d,g[20][20];chara='a';d=creatMGraph_L(G);creatadj(gra,G);vnodev;cout<<endl<<"注意：若该图为非强连通图(含有多个连通分量)时"<<endl<<"最小生成树不存在,则显示为非法值。"<<endl<<endl;cout<<"菜单"<<endl<<endl;cout<<"0、显示该图的邻接矩阵"<<endl;cout<<"1、显示该图的邻接表"<<endl;cout<<"2、深度优先遍历"<<endl;cout<<"3、广度优先遍历"<<endl;cout<<"4、最小生成树PRIM算法"<<endl;cout<<"5、最小生成树KRUScAL算法"<<endl<<end;ints;chary='y';while(y='y'){cout<<"请选择菜单："<<endl;cin>>s;switch(s){case0:cout<<"邻接矩阵显示如下(1代表有，10000代表无)："<<endl;ljjzprint(G);break;case1:cout<<"邻接表显示如下："<<endl;adjprint(gra);break;case3:cout<<"广度优先遍历：";bfstra(gra);cout<<endl;break;case2:cout<<"深度优先遍历：";dfs(gra,0);cout<<endl;break;case4:for(i=0;i!=G.vexnum;++i)for(intj=0;j!=G.vexnum;++j)g[i+1][j+1]=G.arcs[i][j].adj;cout<<"PRIM:"<<endl;PRIM(G,g,d);break;case5:cout<<"kruscal:"<<endl;kruskal(gra);break;}cout<<endl<<"是否继续？y/n:";cin>>y;if(y=='