数据结构图的遍历实验报告

..题目：图的遍历的实现需求分析本演示程序中,输入的数据类型均为整型数据,不允许输入字符等其他数据类型,且需要按照提示内容进行输入,成对的关系数据必须在所建立的图中已经存在对应的结点。演示程序以用户和计算机的对话方式执行,在计算机终端上显示的提示信息的说明下,按照要求输入数据,运算结果在其后显示。本程序实现分别基于邻接矩阵和邻接表存储结构的有、无向图,有、无向网的建立和遍历。遍历分DFS和BFS两种算法,并分别以递归和非递归形式实现。测试数据：无向图结点数4弧数3结点：1234结点关系：12；13；24有向图结点数6弧数6结点：123456结点关系：12；13；24；35；36；25概要设计为实现上述程序功能,图的存储结构分为邻接矩阵和邻接表两种。遍历过程中借助了栈和队列的存储结构。邻接矩阵存储结构的图定义：ADTmgraph{数据对象V：V是具有相同特性的的数据元素的集合,成为顶点集。数据关系R:R=｛VR｝VR={<v,w>|v,wєV且P<v,w>,<v,w>表示从v到w的弧,谓词P<v,w>定义了弧<v,w>的意义或信息}基本操作P：locatevex<G,mes>；初始条件：图G存在,mes和G中顶点有相同的特征。操作结果：若G中存在顶点u,则返回该顶点在图中位置；否则返回其他信息。createudn<&G>；初始条件：图G存在。操作结果：创建无向图。createdn<&G>；初始条件：图G存在。操作结果：创建有向图。createudg<&G>；初始条件：图G存在。操作结果：创建无向网。createdg<&G>；初始条件：图G存在。操作结果：创建有向网。DFS<G,v>；初始条件：图G已经存在并被赋值,v是图中某个顶点的位置坐标。操作结果：深度优先搜索遍历图G,访问顶点时使用函数visit.BFS<G,v>；初始条件：图G已经存在并被赋值,v是图中某个顶点的位置坐标。操作结果：广度优先搜索遍历图G,访问顶点时使用函数visit.visit<a>；初始条件：a为图中的某个顶点值。操作结果：访问顶点a,本程序中作用结果为输出顶点值。｝ADTmgraph邻接表存储结构的图定义：ADTalgraph{数据对象V：V是具有相同特性的的数据元素的集合,成为顶点集。数据关系R:R=｛VR｝VR={<v,w>|v,wєV且P<v,w>,<v,w>表示从v到w的弧,谓词P<v,w>定义了弧<v,w>的意义或信息}基本操作P：locatevex<G,mes>；初始条件：图G存在,mes和G中顶点有相同的特征。操作结果：若G中存在顶点u,则返回该顶点在图中位置；否则返回其他信息。createudn<&G>；初始条件：图G存在。操作结果：创建无向图。createdn<&G>；初始条件：图G存在。操作结果：创建有向图。createudg<&G>；初始条件：图G存在。操作结果：创建无向网。createdg<&G>；初始条件：图G存在。操作结果：创建有向网。DFS<G,v>；初始条件：图G已经存在并被赋值,v是图中某个顶点的位置坐标。操作结果：深度优先搜索遍历图G,访问顶点时使用函数visit.BFS<G,v>；初始条件：图G已经存在并被赋值,v是图中某个顶点的位置坐标。操作结果：广度优先搜索遍历图G,访问顶点时使用函数visit.visit<a>；初始条件：a为图中的某个顶点值。操作结果：访问顶点a,本程序中作用结果为输出顶点值。｝ADTalgraph主程序流程：定义并创建图statuscreatgraph<mgraph&G>{cout<<"请选择构造的图的类型：〔1:有向图,2:有向网,3:无向图,4:无向网"<<endl;intkind;scanf<"%d",&kind>;switch<kind>//通过选择确定创建哪一种图；{case1:returncreatedg<G>;case2:returncreatedn<G>;case3:returncreateudg<G>;case4:returncreateudn<G>;default:returnerror;}}然后采用DFS或BFS进行遍历〔访问结果为输出顶点值。4.函数的调用关系图：maincreatgraphDFS<BFS>createdgcreatedncreateudgcreateudn visitinitstackpushdestroystacklocatevexpopgettopvisitlocatevexlinkqueueenqueuegetheaddequeuedestroyqueue其中,当DFS使用递归算法时相关的栈操作不使用,当BFS使用递归算法时相关的队列操作仍有部分使用。调试分析采用邻接表结构创建图时,由于没有正确进行弧元素的跟进插入,导致图创建不成功。没有采用多文件结构,导致在快要完成时发现函数定义的位置不尽合理,后续添加功能时难度增大。本程序主要为实现遍历算法思想,对实用性考虑偏少,但考虑到了多种数据类型情况下的分别实现,函数拆分较详细,算法可靠性强。算法的时空分析由于对顶点元素的存储均采用了线性结构,所以在创建图和遍历时多依赖于该线性存储的大小。当结点个数为n,弧条数为e时,createdgcreatedncreateudgcreateudn的算法时间复杂度都为O<n²+e*n>,其中对邻接矩阵的初始化耗费了O<n²的时间。当用二维数组表示邻接矩阵作为图的存储结构时,查找每个顶点的邻接点所需时间为O<n²,而以邻接表为存储结构时为O<e。以邻接表为存储结构时,深度优先搜索遍历图〔DFS的时间复杂度为O<n+e>。广度优先搜索遍历图〔BFS的时间复杂度和深度优先搜索遍历〔DFS相同。5.对链表的操作需要很重要的一个量来定位链表和定位操作的位置,指针的作用不可替代。多种数据结构的联合使用在程序中非常重要,多种存储结构的程序实现原理上相同,但具体的操作技巧有很大差别。用户使用说明本程序运行环境建议为windowxp.打开程序工程,并运行其中可执行文件,终端对话框会出现文字提示,请严格按照文字提示进行输入操作。数据之间的分隔可用空格或回车键执行。如下图是某无向图的创建并进行DFS的结果：结果随后出现按照文字提示进行输入数据分隔使用空格或回车结果随后出现按照文字提示进行输入数据分隔使用空格或回车测试结果DFS:附录邻接矩阵结构创建图：#include<iostream>#include<string.h>#include<stdio.h>typedefintvertextype;typedefintinfotype;typedefintstatus;typedefintselemtype;#defineerror0#defineok1#defineINFINTYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大定点个数#defineFALSE0#defineTRUE1#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineoverflow-2usingnamespacestd;//弧定义typedefstructarccell{intadj;//infotype*info;}arccell,adjmatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//图定义typedefstruct{vertextypevexs[MAX_VERTEX_NUM];//顶点adjmatrixarcs;//弧矩阵intvexnum,arcnum;}mgraph;intlocatevex<mgraphG,vertextypemes>{for<inti=0;i<G.vexnum;++i>if<mes==G.vexs[i]>returni;return0;}//定位函数//创建无向网statuscreateudn<mgraph&G>{cout<<"请输入无向网的顶点数,弧数："<<endl;//可添加info选项。。。。。。。scanf<"%d%d",&G.vexnum,&G.arcnum>;cout<<"请输入各顶点的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vexs[i]>;//构造顶点for<inti=0;i<G.vexnum;++i>for<intj=0;j<G.vexnum;++j>G.arcs[i][j].adj=0;cout<<"请输入成对的关系顶点数值以及其权值：〔形如：11221"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;intw;scanf<"%d%d%d",&v1,&v2,&w>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;G.arcs[i][j].adj=w;G.arcs[j][i]=G.arcs[i][j];}returnok;}//创建有向网statuscreatedn<mgraph&G>{cout<<"请输入有向网的顶点数,弧数："<<endl;//可添加info选项。。。。。。。scanf<"%d%d",&G.vexnum,&G.arcnum>;cout<<"请输入各顶点的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vexs[i]>;//构造顶点for<inti=0;i<G.vexnum;++i>for<intj=0;j<G.vexnum;++j>G.arcs[i][j].adj=0;cout<<"请输入成对的关系顶点数值以及其权值：〔形如：11221"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;intw;scanf<"%d%d%d",&v1,&v2,&w>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;G.arcs[i][j].adj=w;}returnok;}//创建无向图statuscreateudg<mgraph&G>{cout<<"请输入无向图的顶点数,弧数："<<endl;//可添加info选项。。。。。。。scanf<"%d%d",&G.vexnum,&G.arcnum>;cout<<"请输入各顶点的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vexs[i]>;//构造顶点for<inti=0;i<G.vexnum;++i>for<intj=0;j<G.vexnum;++j>G.arcs[i][j].adj=0;cout<<"请输入成对的关系顶点数值：〔形如：1122"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;scanf<"%d%d",&v1,&v2>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;G.arcs[i][j].adj=1;G.arcs[j][i]=G.arcs[i][j];}returnok;}//创建有向图statuscreatedg<mgraph&G>{cout<<"请输入有向图的顶点数,弧数："<<endl;//可添加info选项。。。。。。。scanf<"%d%d",&G.vexnum,&G.arcnum>;cout<<"请输入各顶点的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vexs[i]>;//构造顶点for<inti=0;i<G.vexnum;++i>for<intj=0;j<G.vexnum;++j>G.arcs[i][j].adj=0;cout<<"请输入成对的关系顶点数值：〔形如：1122"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;scanf<"%d%d",&v1,&v2>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;G.arcs[i][j].adj=1;}returnok;}邻接矩阵的DFS非递归算法：voidvisit<vertextypea>{printf<"--%d-",a>;}voidDFS<mgraphG,intv>{intvisitp[MAX_VERTEX_NUM];sqstackS;if<initstack<S>==1>;for<inti=0;i<G.vexnum;i++>visitp[i]=FALSE;//首先访问第一个顶点visit<G.vexs[v]>;visitp[v]=TRUE;push<S,G.vexs[v]>;while<S.top!=S.base>//若栈不为空,则继续从栈顶元素进行遍历{intk=0,m=0,num=0,j=0,temp=0;gettop<S,k>;m=locatevex<G,k>;//得到栈顶元素,并在图中定位for<j=0;j<G.vexnum;j++>if<<G.arcs[m][j].adj>!=0&&visitp[j]==FALSE>num+=1;if<num==0>//如果与栈顶元素相关联的顶点都被访问过,则删除栈顶元素pop<S,temp>;//如果与栈顶元素相关联的顶点还有未被访问的,//则将与其相关联的顶点全部访问elsefor<intw=0;w<G.vexnum;w++>if<G.arcs[m][w].adj!=0&&visitp[w]==FALSE>{visit<G.vexs[w]>;//执行visit操作visitp[w]=TRUE;//访问标志置真push<S,G.vexs[w]>;//刚访问的顶点入栈break;}}destroystack<S>;}邻接矩阵的DFS递归算法：intvisitp[MAX_VERTEX_NUM];//全局变量,//注意在main函数中都赋初值FALSEvoidvisit<vertextypea>{printf<"--%d-",a>;}voidDFS<mgraphG,intv>{visit<G.vexs[v]>;visitp[v]=TRUE;for<intj=0;j<G.vexnum;j++>if<<G.arcs[v][j].adj>!=0&&visitp[j]==FALSE>DFS<G,j>;}邻接矩阵存储结构的BFS非递归算法：voidvisit<vertextypea>{printf<"--%d-",a>;}voidBFS<mgraphG,intv>{intvisitp[MAX_VERTEX_NUM];linkqueueQ;if<initqueue<Q>==1>for<inti=0;i<G.vexnum;i++>visitp[i]=FALSE;elseexit<1>;//首先访问第一个顶点visit<G.vexs[v]>;visitp[v]=TRUE;enqueue<Q,G.vexs[v]>;while<Q.front!=Q.rear>{intk=0,m=0,num=0,temp=0,j=0;gethead<Q,k>;m=locatevex<G,k>;//得到队首元素并定位for<j=0;j<G.vexnum;j++>if<<G.arcs[m][j].adj>!=0&&visitp[j]==FALSE>num+=1;if<num==0>dequeue<Q,temp>;//如果此顶点的后继均访问过,则从队列中删除else{for<intw=0;w<G.vexnum;w++>if<G.arcs[m][w].adj!=0&&visitp[w]==FALSE>{visit<G.vexs[w]>;//执行visit操作visitp[w]=TRUE;//访问标志置真enqueue<Q,G.vexs[w]>;}}}destroyqueue<Q>;}邻接矩阵存储结构的BFS递归算法：voidBFS<mgraphG,intv>{linkqueueQ;initqueue<Q>;if<visitp[v]==FALSE>{visit<G.vexs[v]>;visitp[v]=TRUE;}intj;inte;intaddress;for<j=0;j<G.vexnum;j++>if<<G.arcs[v][j].adj>!=0&&visitp[j]==FALSE>{visit<G.vexs[j]>;visitp[j]=TRUE;enqueue<Q,G.vexs[j]>;}while<Q.front!=Q.rear>{dequeue<Q,e>;address=locatevex<G,e>;BFS<G,address>;}destroyqueue<Q>;}intmain<>{mgraphG;creatgraph<G>;inti;for<i=0;i<G.vexnum;i++>visitp[i]=FALSE;BFS<G,0>;return0;}邻接表存储结构的图的创建：#include<stdio.h>#include<iostream>#include<stdlib.h>typedefintvertextype;typedefintinfotype;typedefintstatus;typedefintselemtype;#defineFALSE0#defineTRUE1#defineerror0#defineok1#defineMAX_VERTEX_NUM20//最大顶点个数#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineoverflow-2usingnamespacestd;typedefstructarcnode{ intadjvex;//弧指向的顶点的位置 intadj;//权值 structarcnode*nextrarc;//指向下一条弧的指针 infotype*info;}arcnode;//顶点结点定义typedefstructvnode{ vertextypedata;//顶点数据 arcnode*firsttarc;//指向第一条依附该顶点的弧的指针}vnode,adjlist[MAX_VERTEX_NUM];//图定义typedefstruct{ adjlistvertices;//顶点数组 intvexnum,arcnum;//顶点数目,弧数目 intkind;//图的种类标志,以数字代表}algraph;intlocatevex<algraphG,vertextypemes>{for<inti=0;i<G.vexnum;++i>if<mes==G.vertices[i].data>returni;return-1;}//创建无向网statuscreateudn<algraph&G>{cout<<"请输入无向网的顶点数,弧数："<<endl;scanf<"%d%d",&G.vexnum,&G.arcnum>;//输入顶点数和弧数cout<<"请输入各顶点的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vertices[i].data>;//输入并构造顶点for<inti=0;i<G.vexnum;++i>G.vertices[i].firsttarc=NULL;//初始化指针firsttarccout<<"请输入成对的关系顶点数值以及其权值：〔形如：11221"<<endl;for<intk=0;k<G.arcnum;++k>//输入相联系的两数据{vertextypev1,v2;intw;//权值scanf<"%d%d%d",&v1,&v2,&w>;getchar<>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;//定位arcnode*a;a=<arcnode*>malloc<sizeof<arcnode>>;//为加入的弧结点申请空间if<a==NULL>exit<1>;<*a>.adjvex=j;<*a>.adj=w;<*a>.nextrarc=NULL;<*a>.info=NULL;if<G.vertices[i].firsttarc==NULL>G.vertices[i].firsttarc=a;//当此弧是顶点i的第一条弧时else//当此弧不是顶点i的第一条弧时{a->nextrarc=G.vertices[i].firsttarc->nextrarc;G.vertices[i].firsttarc=a;}//处理另一条对称的顶点jif<G.vertices[j].firsttarc==NULL>G.vertices[j].firsttarc=a;//当此弧是顶点j的第一条弧时else//当此弧不是顶点j的第一条弧时{a->nextrarc=G.vertices[j].firsttarc->nextrarc;G.vertices[j].firsttarc=a;}}returnok;}//有向网statuscreatedn<algraph&G>{cout<<"请输入有向网的顶点数,弧数："<<endl;scanf<"%d%d",&G.vexnum,&G.arcnum>;cout<<"请输入各顶点的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vertices[i].data>;//构造顶点for<inti=0;i<G.vexnum;++i>G.vertices[i].firsttarc=NULL;//初始化指针firsttarccout<<"请输入成对的关系顶点数值以及其权值：〔形如：11221"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;intw;scanf<"%d%d%d",&v1,&v2,&w>;getchar<>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;arcnode*a;a=<arcnode*>malloc<sizeof<arcnode>>;if<a==NULL>exit<1>;<*a>.adjvex=j;<*a>.adj=w;<*a>.nextrarc=NULL;<*a>.info=NULL;if<G.vertices[i].firsttarc==NULL>G.vertices[i].firsttarc=a;//当此弧是顶点i的第一条弧时else//当此弧不是顶点i的第一条弧时连接到第一条弧位置,将原来的弧接到后面{a->nextrarc=G.vertices[i].firsttarc->nextrarc;G.vertices[i].firsttarc=a;}}returnok;}//无向图statuscreateudg<algraph&G>{cout<<"请输入无向图的顶点数,弧数："<<endl;scanf<"%d%d",&G.vexnum,&G.arcnum>;getchar<>;cout<<"请输入各顶点的值："<<endl;for<inti=0;i<G.vexnum;++i>{scanf<"%d",&G.vertices[i].data>;}//顶点赋值getchar<>;for<inti=0;i<G.vexnum;++i>G.vertices[i].firsttarc=NULL;//初始化指针firsttarccout<<"请输入成对的关系顶点数值：〔形如：1122"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;scanf<"%d%d",&v1,&v2>;getchar<>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;arcnode*a;a=<arcnode*>malloc<sizeof<arcnode>>;//为加入的弧结点申请空间if<a==NULL>exit<1>;<*a>.adjvex=j;<*a>.adj=1;<*a>.nextrarc=NULL;<*a>.info=NULL;if<G.vertices[i].firsttarc==NULL>//当此弧是顶点i的第一条弧时{G.vertices[i].firsttarc=a;//cout<<"attachtofirsttarc"<<endl;}else//当此弧不是顶点i的第一条弧时{a->nextrarc=G.vertices[i].firsttarc;G.vertices[i].firsttarc=a;//cout<<"attachsuccessfully!"<<endl;}//处理对称的另一个顶点if<G.vertices[j].firsttarc==NULL>//当此弧是顶点j的第一条弧时{G.vertices[j].firsttarc=a;//cout<<"attachtofirsttarc"<<endl;}else//当此弧不是顶点j的第一条弧时{a->nextrarc=G.vertices[j].firsttarc;G.vertices[j].firsttarc=a;//cout<<"attachsuccessfully!"<<endl;}}returnok;}statuscreatedg<algraph&G>{cout<<"请输入无向图的顶点数,弧数："<<endl;scanf<"%d%d",&G.vexnum,&G.arcnum>;getchar<>;cout<<"请输入各顶点的值："<<endl;for<inti=0;i<G.vexnum;++i>{scanf<"%d",&G.vertices[i].data>;}//顶点赋值getchar<>;for<inti=0;i<G.vexnum;++i>G.vertices[i].firsttarc=NULL;//初始化指针firsttarccout<<"请输入成对的关系顶点数值：〔形如：1122"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;scanf<"%d%d",&v1,&v2>;getchar<>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;arcnode*a;a=<arcnode*>malloc<sizeof<arcnode>>;//为加入的弧结点申请空间if<a==NULL>exit<1>;<*a>.adjvex=j;<*a>.adj=1;<*a>.nextrarc=NULL;<*a>.info=NULL;if<G.vertices[i].firsttarc==NULL>//当此弧是顶点i的第一条弧时{G.vertices[i].firsttarc=a;//cout<<"attachtofirsttarc"<<endl;}else//当此弧不是顶点i的第一条弧时{a->nextrarc=G.vertices[i].firsttarc;G.vertices[i].firsttarc=a;//cout<<"attachsuccessfully!"<<endl;}}returnok;}邻接表存储结构的额DFS非递归算法：//visit函数voidvisit<vertextypea>{printf<"--%d-",a>;}//DFSvoidDFS<algraphG,intv>{intvisitp[MAX_VERTEX_NUM];//访问标记数组,sqstackS;initstack<S>;//建立存储访问过结点的栈for<inti=0;i<G.vexnum;i++>visitp[i]=FALSE;//将各顶点访问标记均赋值为FALSEvisit<G.vertices[v].data>;visitp[v]=TRUE;push<S,G.vertices[v].data>;//访问并入栈第一个顶点while<S.base!=S.top>//当栈不为空时进行遍历{arcnode*p;intnum=0,temp=0,k=0,m=0;gettop<S,k>;//得到栈顶元素m=locatevex<G,k>;//定位栈顶元素在图中的坐标for<p=G.vertices[m].firsttarc;p!=NULL;p=p->nextrarc>{if<visitp[<*p>.adjvex]==FALSE>num+=1;}//cout<<"thereare"<<num<<"pointleft"<<endl;if<num==0>//如果此顶点的后继顶点都被访问过,则从栈中删除此顶点{pop<S,temp>;cout<<"nopointleft"<<endl;}else{for<p=G.vertices[m].firsttarc;p!=NULL;p=p->nextrarc>if<visitp[<*p>.adjvex]==FALSE>{visit<G.vertices[<*p>.adjvex].data>;visitp[<*p>.adjvex]=TRUE;push<S,G.vertices[<*p>.adjvex].data>;break;//因为是深度优先,所以遇到可访问顶点并访问后跳出for循环}}}destroystack<S>;//销毁辅助栈}邻接表存储结构的DFS递归算法：intvisitp[MAX_VERTEX_NUM];//全局变量,//注意在main函数中都赋初值FALSEvoidvisit<vertextypea>{printf<"--%d-",a>;}voidDFS<algraphG,intv>{visit<G.vertices[v].data>;visitp[v]=TRUE;for<arcnode*p=G.vertices[v].firsttarc;p!=NULL;p=p->nextrarc>if<visitp[p->adjvex]==FALSE>DFS<G,p->adjvex>;}intmain<>{algraphG;createudg<G>;for<inti=0;i<MAX_VERTEX_NUM;i++>visitp[i]=FALSE;DFS<G,0>;return0;}邻接表存储结构的BFS非递归算法：voidvisit<vertextypea>{printf<"--%d-",a>;}voidBFS<algraphG,intv>{intvisitp[MAX_VERTEX_NUM];linkqueueQ;if<initqueue<Q>==1>for<inti=0;i<MAX_VERTEX_NUM;i++>visitp[i]=FALSE;elseexit<1>;//首先访问第一个顶点visit<G.vertices[v].data>;visitp[v]=TRUE;enqueue<Q,G.vertices[v].data>;while<Q.front!=Q.rear>{intk=0,m=0,num=0,temp=0;gethead<Q,k>;m=locatevex<G,k>;//得到队首元素并定位for<arcnode*j=G.vertices[m].firsttarc;j!=NULL;j=j->nextrarc>if<visitp[<*j>.adjvex]==FALSE>num+=1;if<num==0>dequeue<Q,temp>;//如果此顶点的后继均访问过,则从队列中删除else{for<arcnode*p=G.vertices[m].firsttarc;p!=NULL;p=p->nextrarc>if<visitp[<*p>.adjvex]==FALSE>{visit<G.vertices[<*p>.adjvex].data>;//执行visit操作visitp[<*p>.adjvex]=TRUE;//访问标志置真enqueue<Q,G.vertices[<*p>.adjvex].data>;}}}destroyqueue<Q>;}intmain<>{algraphG;createudg<G>;BFS<G,0>;return0;}//邻接表存储结构的BFS递归算法voidvisit<vertextypea>{printf<"--%d-",a>;}intvisitp[MAX_VERTEX_NUM];voidBFS<algraphG,intv>{linkqueueQ;initqueue<Q>;if<visitp[v]==FALSE>{visit<G.vertices[v].data>;visitp[v]=TRUE;}//访问标记,inte;intaddress;arcnode*p;for<p=G.vertices[v].firsttarc;p!=NULL;p=p->nextrarc>if<visitp[<*p>.adjvex]==FALSE>{visit<G.vertices[<*p>.adjvex].data>;visitp[<*p>.adjvex]=TRUE;enqueue<Q,G.vertices[<*p>.adjvex].data>;}//访问该与结点有关系的全部结点while<Q.front!=Q.rear>{dequeue<Q,e>;address=locatevex<G,e>;BFS<G,address>;//递归调用BFS}destroyqueue<Q>;}intmain<>{algraphG;createudg<G>;inti;for<i=0;i<MAX_VERTEX_NUM;i++>visitp[i]=FALSE;BFS<G,0>;return0;}辅助队列的实现：#include<iostream>#include<string.h>#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefintvertextype;typedefintinfotype;typedefintstatus;typedefintqelemtype;#defineerror0#defineok1#defineINFINTYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大定点个数#defineoverflow-2#defineFALSE0#defineTRUE1usingnamespacestd;typedefstructqnode{qelemtypedata;structqnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;//队头指针queueptrrear;//队尾指针}linkqueue;statusinitqueue<linkqueue&Q>;statusgethead<linkqueueQ,qelemtype&e>;statusenqueue<linkqueue&Q,qelemtypee>;statusdequeue<linkqueue&Q,qelemtype&e>;statusdestroyqueue<linkqueue&Q>;statusinitqueue<linkqueue&Q>{Q.front=Q.rear=<queueptr>malloc<sizeof<qnode>>;if<!Q.front>exit<overflow>;Q.front->next=NULL;returnok;}statusgethead<linkqueueQ,qelemtype&e>{if<Q.front==Q.rear>returnerror;e=Q.front->next->data;returnok;}statusenqueue<linkqueue&Q,qelemtypee>{queueptrp;p=<queueptr>mal