图的遍历和生成树求解实现 课程设计报告

中北大学数据结构课程设计说明书

学生姓名:郭燕文学号：1021011720学院:软件学院专业:软件工程题目:图的遍历和生成树求解实现成绩指导教师尹四清、薛海丽

2011年12月19日设计目的：《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2设计内容和要求设计内容：采用合适的存储结构来创建图，并实现图的遍历；（2）计算图的最小生成树，求联通分量设计要求：（1）先任意创建一个图；（2)

图的DFS,BFS的递归和非递归算法的实现（3)

最小生成树（两个算法）的实现，求连通分量的实现（4)

要求用邻接矩阵、邻接表、十字链表多种结构存储实现3．本设计所采用的数据结构：本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。4.1详细设计思想这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。开始开始创建图G表存储图Ify=’y’NY显示图的邻接矩阵KRUSCAL算法显示图的邻接表深度优先遍历广度优先遍历最小生成树PRIM输入字母Ify=’y’结束NY图的连通分量输入一个数20134564.3核心代码#include<iostream>#include<malloc.h>usingnamespacestd;#defineint_max10000#defineinf9999#definemax20//…………邻接矩阵定义……typedefstructArcCell22{ intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];AdjMatrixarcs;intvexnum,arcnum;//有向图的当前顶点数和弧数}MGraph_L;//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^intlocalvex(MGraph_LG,charv)//返回V的位置{inti=0;while(G.vexs[i]!=v){++i;}returni;}intcreatMGraph_L(MGraph_L&G)//创建图用邻接矩阵表示{charv1,v2;inti,j,w;cout<<"…………创建无向图…………"<<endl<<"请输入图G顶点和弧的个数:(46)不包括"<<endl;cin>>G.vexnum>>G.arcnum;for(i=0;i!=G.vexnum;++i){cout<<"输入顶点"<<i<<endl;cin>>G.vexs[i];}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(intk=0;k!=G.arcnum;++k){cout<<"输入一条边依附的顶点和权:(ab3)不包括"<<endl;cin>>v1>>v2>>w;//输入一条边依附的两点及权值i=localvex(G,v1);//确定顶点V1和V2在图中的位置j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}cout<<"图G邻接矩阵创建成功！"<<endl;returnG.vexnum;}voidljjzprint(MGraph_LG){inti,j;for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j)cout<<G.arcs[i][j].adj<<"";cout<<endl;}}intvisited[max];//访问标记intwe;typedefstructarcnode//弧结点{intadjvex;//该弧指向的顶点的位置structarcnode*nextarc;//弧尾相同的下一条弧char*info;//该弧信息}arcnode;typedefstructvnode//邻接链表顶点头接点{chardata;//结点信息arcnode*firstarc;//指向第一条依附该结点的弧的指针}vnode,adjlist;typedefstruct//图的定义{adjlistvertices[max];intvexnum,arcnum;intkind;}algraph;//…………队列定义……typedefstructqnode{intdata;structqnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;//………………………typedefstructacr{intpre;//弧的一结点intbak;//弧另一结点intweight;//弧的权}edg;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->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->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=p->nextarc;}cout<<endl;}*/cout<<"图G邻接表创建成功！"<<endl;return1;}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;}}intfirstadjvex(algraphgra,vnodev)//返回依附顶点V的第一个点//即以V为尾的第一个结点{if(v.firstarc!=NULL)returnv.firstarc->adjvex;}intnextadjvex(algraphgra,vnodev,intw)//返回依附顶点V的相对于W的下一个顶点{arcnode*p;p=v.firstarc;while(p!=NULL&&p->adjvex!=w){p=p->nextarc;}if(p->adjvex==w&&p->nextarc!=NULL){p=p->nextarc;returnp->adjvex;}if(p->adjvex==w&&p->nextarc==NULL)return-10;}intinitqueue(linkqueue&q)//初始化队列{q.rear=(queueptr)malloc(sizeof(qnode));q.front=q.rear;if(!q.front)return0;q.front->next=NULL;return1;}intenqueue(linkqueue&q,inte)//入队{queueptrp;p=(queueptr)malloc(sizeof(qnode));if(!p)return0;p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return1;}intdequeue(linkqueue&q,int&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;}intqueueempty(linkqueueq)//判断队为空{if(q.front==q.rear)return1;return0;}voidbfstra(algraphgra)//广度优先遍历{inti,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);//cout<<""<<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);}}}}}intdfs(algraphgra,inti);//声明DFSintdfstra(algraphgra){inti,j;for(i=0;i!=gra.vexnum;++i){visited[i]=0;}for(j=0;j!=gra.vexnum;++j){if(visited[j]==0)dfs(gra,j);}return0;}intdfs(algraphgra,inti){visited[i]=1;intwe1;//cout<<i<<visited[i]<<endl;cout<<gra.vertices[i].data;//cout<<endl;for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we)){//cout<<we<<visited[we]<<endl;we1=we;//cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;if(visited[we]==0)//cout<<dfs(gra,we);//<<endl;//cout<<i<<we1<<endl;we=we1;//cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;}return12;}intbfstra_fen(algraphgra)//求连通分量{inti,j;for(i=0;i!=gra.vexnum;++i){visited[i]=0;}for(j=0;j!=gra.vexnum;++j){if(visited[j]==0){dfs(gra,j);cout<<endl;}}return0;}typedefstruct{intadjvex;intlowcost;}closedge;/*intminimum(closedge*p);intminispantree(MGraph_LG,charu){intk,j,i;closedgeclosedge_a[20];k=localvex(G,u);//cout<<k<<endl;for(j=0;j!=G.vexnum;++j){if(j!=k){closedge_a[j].adjvex=u;closedge_a[j].lowcost=G.arcs[k][j].adj;}for(i=1;i!=G.vexnum;++i){k=minimum(closedge_a);cout<<k;cout<<closedge_a[k].adjvex<<""<<G.vexs[k]<<endl;closedge_a[k].lowcost=0;for(j=0;j!=G.vexnum;++j)if(G.arcs[k][j].adj<closedge_a[j].lowcost){closedge_a[j].adjvex=G.vexs[k];closedge_a[j].lowcost=G.arcs[k][j].adj;}}}return0;}intminimum(closedge*p){ints=10000;for(;p!=NULL;++p){if(s>p->lowcost)s=p->lowcost;}returns;}*/intprim(intg[][max],intn)//最小生成树PRIM算法{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;}printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);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;}printf("\n");}return0;}intacrvisited[100];//kruscal弧标记数组intfind(intacrvisited[],intf){while(acrvisited[f]>0)f=acrvisited[f];returnf;}voidkruscal_arc(MGraph_LG,algraphgra){edgedgs[20];inti,j,k=0;for(i=0;i!=G.vexnum;++i)for(j=i;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=G.arcs[i][j].adj;++k;}}intx,y,m,n;intbuf,edf;for(i=0;i!=gra.arcnum;++i)acrvisited[i]=0;for(j=0;j!=G.arcnum;++j){m=10000;for(i=0;i!=G.arcnum;++i){if(edgs[i].weight<m){m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}//cout<<x<<y<<m;//cout<<endl;buf=find(acrvisited,x);edf=find(acrvisited,y);//cout<<buf<<""<<edf<<endl;edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}voidmain(){algraphgra;MGraph_LG;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;cout<<"6、该图的连通分量………"<<endl<<endl;ints;chary='y';while(y='y'){cout<<"请选择菜单："<<endl;cin>>s;switch(s){case0:cout<<"邻接矩阵显示如下："<<endl;ljjzprint(G);break;case1:cout<<"邻接表显示如下："<<endl;adjprint(gra);break;case2:cout<<"广度优先遍历：";bfstra(gra);cout<<endl;break;case3:for(i=0;i!=