图的遍历和生成树求解实现的课程结构设计 33页

'图的遍历和生成树求解实现的课程结构设计一.问题描述：1.图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。2.基本功能1)先任意创建一个图；2)图的DFS,BFS的递归和非递归算法的实现3)最小生成树（两个算法）的实现，求连通分量的实现4)要求用邻接矩阵、邻接表等多种结构存储实现3.输入输出输入数据类型为整型和字符型，输出为整型和字符二、概要设计1.设计思路：a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。32 2.数据结构设计：ADTQueue{数据对象：D={ai|ai∈ElemSet,i=1,2,3……，n,n≥0}数据关系：R1={|ai-1,ai∈D,i=1,2,3,……，n}基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。QueueEmpty(Q)初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。EnQueue(&Q,e)初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADTQueueADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={|v,w∈V且P（v，w）,表示从v到w的弧，谓词P（v,w）定义了弧的意义或信息}基本操作P：CreatGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。BFSTraverse(G,visit());初始条件：图G存在，Visit是定点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败。DFSTraverse(G,visit());初始条件：图G存在，Visit是定点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit（）失32 败，则操作失败。DFStra_fen(G)初始条件：图G存在，存在图的深度优先遍历算法。操作结果：从多个顶点对图进行深度优先遍历，得到连通分量。}ADTGraph;3.软件结构设计：函数名返回值类型creatMGraph_L(G)intcreatadj(gra,G)intljjzprint(G)voidadjprint(gra,G)voidBFSTraverse(gra)voidDFStra(gra)intDFSTraverse_fen(gra)intMiniSpanTree_PRIM(g,G.vexnum)intMiniSpanTREE_KRUSCAL(G,gra)void三、详细设计1.定义程序中所有用到的数据及其数据结构，及其基本操作的实现；邻接矩阵定义:typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[max][max];typedefstruct{VertexTypevexs[max];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}MGraph_L;32 邻接表的定义:typedefstructArcNode//弧结点{intadjvex;//该弧指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;typedefstructVNode//邻接链表顶点头接点{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList;typedefstruct//图的定义{AdjListvertices[max];intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;队列定义:typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;2．主函数和其他函数的伪码算法；主函数：intmain(){ints;chary="y";cout<<"||¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤菜单¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<>s;if(s==0){++o;if(o==2){n=0;l=0;o=0;}}switch(s){case0:cout<<"创建一个无向图："<0){cout<<"若该图为非强连通图(含有多个连通分量)时，最小生成树不存在"<0){cout<<"该图为非强连通图(含有多个连通分量)，最小生成树不存在"<>y;if(y=="n")break;}return0;}邻接矩阵存储：intcreatMGraph_L(MGraph_L&G)//创建图用邻接矩阵表示{charv1,v2;inti,j,w;cout<<"请输入顶点和弧的个数"<>G.vexnum>>G.arcnum;cout<<"输入各个顶点"<>G.vexs[i];}for(i=0;i>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;}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=1&&G.arcs[i][j].adj=1)cout<<"这是一个有权图"<adjvex=j;arc->nextarc=gra.vertices[i].firstarc;gra.vertices[i].firstarc=arc;}}gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;32 cout<<"图G邻接表创建成功！"<"<<"["<adjvex<<"]";p=p->nextarc;}cout<<"->"<<"End";cout<next=NULL;return1;}入队：StatusEnQueue(LinkQueue&Q,QElemTypee)//入队,插入元素e为Q的新的队尾元素{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)return0;//存储分配失败32 p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return1;}出队：StatusDeQueue(LinkQueue&Q,QElemType&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;}判断队为空：StatusQueueEmpty(LinkQueueQ)//判断队为空{if(Q.front==Q.rear)return1;return0;}广度优先遍历：voidBFSTraverse(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<=0;we=nextadjvex(gra,gra.vertices[e],we)){if(!visited[we]){visited[we]=1;cout<=0;we=nextadjvex(gra,gra.vertices[i],we)){we1=we;if(visited[we]==0)DFS(gra,we);we=we1;}return1;}intDFStra(ALGraphgra){inti,j;32 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;}连通分量：intDFSTraverse_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<0为有权图，此时输出的时候用∞代替10000；n=0为无权图，此时输出的时候用0代替10000.b.程序中有的功能对某些图是不适用的，比如无权图没有最小生成树，非强连通图没有最小生成树等。所以在程序中又新增了全局变量l,l>0时表示为非强连通图，则在求最小生成树时报错。C.当程序先创建一个有权图后，n的值会大于1，第二次创无权图时也会被程序认为有权图，所以在程序中在定义全局变量o（初值为0）,来判断创建了几次图，当第二次创建图，即o=2时，所有全局变量在开始全归零。4.程序中可以改进的地方说明；当建立一个图时先得求其连通分量，从而确定全局变量l的值，从而才能判断该图是否有最小生成树。32 五、测试结果创建一个无权图：32 创建一个费强连通的有权图：32 创建一个有权连通图：32 六、用户手册a.先选0创建一个图。b.选择y继续操作。c.按照菜单编码选择操作。七、体会与自我评价在做这个程序的时候你首先必须知道图的一些概念，图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。当我们拿到一个图时，我们对该图的遍历就要有一些方法，所以有了深度优先遍历和广度优先遍历，我们要明白这两种遍历是怎么实现的，然后根据我们人脑中的方法把它写成电脑算法。对一个图我们还定义了连通分量，所以将图存到电脑中时，我们对连通分量得有个算法。求图的最小生成树有两种算法，普利姆是从结点出发寻找权最小的边，知道所有结点都练通了；而克鲁斯卡尔算法则是从边出发，寻找使图连通的权值最小边的方法。算法的实现从人脑到电脑的转变是比较复杂的一件事，要求做到具体到实现该方法的每一个步骤，然后再将每一个步骤通过代码实现。这要求我们要明确各个数据元素和个元素之间的关系，然后才能明确使用算法去调用这些数据。通过本次的课程设计，我对数据结构有了一定的认识，明白了数据结构中数据，数据关系，及对其操作的方法。但同时也发现在自己有很多的不足，在使用语言和如何精炼语言需要进行更多的训练。源代码：#include32 #includeusingnamespacestd;#defineint_max10000//最大值staticintn=0;//全局变量，判断有权图和无权图staticinto=0;//全局变量，清除BUGstaticintl=0;//全局变量，清除BUG#defineinf9999//最小值的最大值#definemax20//最大顶点个数typedefintVRType,QElemType,Status;typedefcharInfoType,VertexType;//|||||||||||||||||||||||||邻接矩阵|||||||||||||||||||||||||||||||//----------------------------邻接矩阵定义-------------------------typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[max][max];typedefstruct{VertexTypevexs[max];//顶点向量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<<"请输入顶点和弧的个数"<>G.vexnum>>G.arcnum;cout<<"输入各个顶点"<>G.vexs[i];}for(i=0;i>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;}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=1&&G.arcs[i][j].adj=1)cout<<"这是一个有权图"<adjvex=j;32 arc->nextarc=gra.vertices[i].firstarc;gra.vertices[i].firstarc=arc;}}gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout<<"图G邻接表创建成功！"<"<<"["<adjvex<<"]";p=p->nextarc;}cout<<"->"<<"End";cout<next=NULL;return1;}StatusEnQueue(LinkQueue&Q,QElemTypee)//入队,插入元素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;}StatusDeQueue(LinkQueue&Q,QElemType&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;}StatusQueueEmpty(LinkQueueQ)//判断队为空{if(Q.front==Q.rear)return1;return0;}//----------------------------图的遍历----------------------------intvisited[max];//访问标记intwe;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){32 p=p->nextarc;}if(p->adjvex==w&&p->nextarc!=NULL){p=p->nextarc;returnp->adjvex;}if(p->adjvex==w&&p->nextarc==NULL)return-10;}//----------------------------广度优先遍历----------------------------voidBFSTraverse(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<=0;we=nextadjvex(gra,gra.vertices[e],we)){if(!visited[we]){visited[we]=1;cout<=0;we=nextadjvex(gra,gra.vertices[i],we)){we1=we;if(visited[we]==0)DFS(gra,we);we=we1;}return1;}intDFStra(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;}//----------------------------求连通分量------------------------------intDFSTraverse_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<0)f=acrvisited[f];returnf;}typedefstructacr32 {intpre;//弧的一结点intbak;//弧另一结点intweight;//弧的权}edg;voidMiniSpanTREE_KRUSCAL(MGraph_LG,ALGraphgra){edgedgs[max];inti,j,k=0;for(i=0;i!=G.vexnum;++i)for(j=i;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=int_max){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=int_max;for(i=0;i!=G.arcnum;++i){if(edgs[i].weight>s;if(s==0){++o;if(o==2){n=0;l=0;o=0;}}switch(s){case0:cout<<"创建一个无向图："<1){cout<<"若该图为非强连通图(含有多个连通分量)时，最小生成树不存在"<1){cout<<"该图为非强连通图(含有多个连通分量)，最小生成树不存在"<>y;if(y=="n")break;}return0;}32'