图遍历的演示实习报告

图遍历的演示题目:诸多波及图上操作的算法都是以图的遍历操作为基础的。试设计一种程序,演示在连通和非连通的无向图上访问所有结点的操作一、需求分析1、以邻接多重表为存储构造；2、实现连通和非连通的无向图的深度优先和广度优先遍历；3、以顾客指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集；二、概要设计1、设定图的抽象数据类型:ADTGraph{数据对象V:V是具有相似特性的数据元素的集合,称为点集.数据关系R:R={VR}VR={(v,w)|v,w属于V,(v,w)表达v和w之间存在的途径}基本操作P:CreatGraph(&G,V,VR)初始条件:V是图的顶点集,VR是图中弧的集合.操作成果:按V和VR是定义构造图G.DestroyGraph(&G)初始条件:图G存在操作成果:销毁图GLocateVex(G,u)初始条件:图G存在,u和G中顶点有相似的特性操作成果:若图G中存在顶点u,则返回该顶点在图中的位置;否则返回其他信息GetVex(G,v)初始条件:图G存在,v是G中顶点操作成果:返回v的值FirstAjvex(G,v)初始条件:图G存在,v是G中顶点操作成果:返回v的第一种邻接顶点,若顶在图中没有邻接顶点,则返回为空NextAjvex(G,v,w)初始条件:图G存在,v是G中顶点,w是v的邻接顶点操作成果:返回v的下一种邻接顶点,若w是v的最终一种邻接顶点,则返回空DeleteVexx(&G,v)初始条件:图G存在,v是G中顶点操作成果:删除顶点v已经其有关的弧DFSTraverse(G,visit())初始条件:图G存在,visit的顶点的应用函数操作成果:对图进行深度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败BFSTraverse(G,visit())初始条件:图G存在,visit的顶点的应用函数操作成果:对图进行广度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败}ADTGraph2、设定栈的抽象数据类型：ADTStack{数据对象：D={ai|ai∈CharSet，i=1，2，……，n，n≥0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2，……，n}基本操作：InitStack(&S)操作成果：构造一种空栈S。DestroyStack(&S)初始条件：栈S已存在。操作成果：栈S被销毁。Push(&S,e);初始条件：栈S已存在。操作成果：在栈S的栈顶插入新的栈顶元素e。Pop(&S,e);初始条件：栈S已存在。操作成果：删除S的栈顶元素，并以e返回其值。StackEmpty(S)初始条件：栈S已存在。操作成果：若S为空栈，则返回TRUE，否则返回FALSE。}ADTStack3、设定队列的抽象数据类型：ADTQueue{数据对象:D={ai|ai属于Elemset,i=1,2….,n,n>=0}数据关系:R1={<ai-1,ai>|ai-1,ai属于D,i=1,2,…,n}约定ai为端为队列头,an为队列尾基本操作:InitQueue(&Q)操作成果:构造一种空队列QDestryoQueue(&Q)初始条件：队列Q已存在。操作成果：队列Q被销毁，不再存在。EnQueue(&Q,e)初始条件:队列Q已经存在操作成果:插入元素e为Q的新的队尾元素DeQueue(&Q,&E)初始条件:Q为非空队列操作成果:删除Q的队尾元素,并用e返回其值QueueEmpty(Q)初始条件:队列已经存在操作成果:若队列为空,则返回TRUE,否则返回FLASE}ADTQueue4、本程序包括九个模块：主程序模块voidmain(){手动构造一种图；从文献导入一种图；显示图的信息；进行深度优先遍历图；进行广度优先遍历图；保留图到一种文献；寻找途径；销毁一种图；}；手动构造一种图-自己输入图的顶点和边生成一种图；从文献导入一种图；显示图的信息-打印图的所有顶点和边；进行深度优先遍历图-打出遍历的结点序列和边集；进行广度优先遍历图-打出遍历的结点序列和边集；保留图到一种文献；寻找从起点到终点，但中间不通过某点的所有简朴途径；销毁图。三、详细设计顶点,边和图类型#defineMAX_INFO10/*有关信息字符串的最大长度+1*/#defineMAX_VERTEX_NUM20/*图中顶点数的最大值*/typedefcharInfoType;/*有关信息类型*/typedefcharVertexType;/*字符类型*/typedefenum{unvisited,visited}VisitIf;typedefstructEBox{VisitIfmark;/*访问标识*/intivex,jvex;/*该边依附的两个顶点的位置*/structEBox*ilink,*jlink;/*分别指向依附这两个顶点的下一条边*/InfoType*info;/*该边信息指针*/}EBox;typedefstruct{VertexTypedata;EBox*firstedge;/*指向第一条依附该顶点的边*/}VexBox;typedefstruct{VexBoxadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;/*无向图的目前顶点数和边数*/}AMLGraph;图的基本操作如下：intLocateVex(AMLGraphG,VertexTypeu)；//查G和u有相似特性的顶点，若存在则返回该顶点在无向图中位置;否则返回-1。VertexType&GetVex(AMLGraphG,intv)；//以v返回邻接多重表中序号为i的顶点。intFirstAdjVex(AMLGraphG,VertexTypev)；//返回v的第一种邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1。intNextAdjVex(AMLGraphG,VertexTypev,VertexTypew)；//返回v的(相对于w的)下一种邻接顶点的序号若w是v的最终一种邻接点,则返回-1。voidCreateGraph(AMLGraph&G)；//采用邻接多重表存储构造,构造无向图G。StatusDeleteArc(AMLGraph&G,VertexTypev,VertexTypew)；//在G中删除边<v,w>。StatusDeleteVex(AMLGraph&G,VertexTypev)；//在G中删除顶点v及其有关的边。voidDestroyGraph(AMLGraph&G)；//销毁一种图voidDisplay(AMLGraphG)；//输出无向图的邻接多重表G。voidDFSTraverse(AMLGraphG,VertexTypestart,int(*visit)(VertexType))；//从start顶点起,（运用栈非递归）深度优先遍历图G。voidBFSTraverse(AMLGraphG,VertexTypestart,int(*Visit)(VertexType))；//从start顶点起,广度优先遍历图G。voidMarkUnvizited(AMLGraphG)；//置边的访问标识为未被访问。其中部分操作的伪码算法如下：voidCreateGraph(AMLGraph&G){/*采用邻接多重表存储构造,构造无向图G*/DestroyGraph(G);/*假如图不空,先销毁它*/输入无向图的顶点数G.vexnum；输入无向图的边数G.edgenum；输入顶点的信息IncInfo；依次输入无向图的所有顶点；for(k=0;k<G.edgenum;++k)/*构造表结点链表*/{读入两个顶点va、vb；i=LocateVex(G,va);/*一端*/j=LocateVex(G,vb);/*另一端*/p=(EBox*)malloc(sizeof(EBox));p->mark=unvisited;/*设初值*/p->ivex=i;p->jvex=j;p->info=NULL;p->ilink=G.adjmulist[i].firstedge;/*插在表头*/G.adjmulist[i].firstedge=p;p->jlink=G.adjmulist[j].firstedge;/*插在表头*/G.adjmulist[j].firstedge=p;}}voidDisplay(AMLGraphG){/*输出无向图的邻接多重表G*/MarkUnvizited(G);输出无向图的所有顶点；for(i=0;i<G.vexnum;i++){p=G.adjmulist[i].firstedge;while(p)if(p->ivex==i)/*边的i端与该顶点有关*/ { if(!p->mark)/*只输出一次*/ { cout<<G.adjmulist[i].data<<'-'<<G.adjmulist[p->jvex].data<<ends; p->mark=visited; } p=p->ilink; }else/*边的j端与该顶点有关*/ { if(!p->mark)/*只输出一次*/ { cout<<G.adjmulist[p->ivex].data<<'-'<<G.adjmulist[i].data<<ends; p->mark=visited; } p=p->jlink;}cout<<endl;}}voidDFSTraverse(AMLGraphG,VertexTypestart,int(*visit)(VertexType)){/*从start顶点起,深度优先遍历图G(非递归算法)*/InitStack(S);w=LocateVex(G,start);/*先确定起点start在无向图中的位置*/for(v=0;v<G.vexnum;v++)Visited[v]=0;/*置初值*/for(v=0;v<G.vexnum;v++)if(!Visited[(v+w)%G.vexnum]){Push(S,(v+w)%G.vexnum);/*未访问，就进栈*/while(!StackEmpty(S)){Pop(S,u);if(!Visited[u]){Visited[u]=1; /*未访问的标志设为访问状态，并输出它的值*/visit(G.adjmulist[u].data);for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0; w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data)) if(!Visited[w]) Push(S,w);}}}DestroyStack(S);/*销毁栈,释放其空间*/}voidBFSTraverse(AMLGraphG,VertexTypestart,int(*Visit)(VertexType)){/*从start顶点起,广度优先遍历图G*/for(v=0;v<G.vexnum;v++)Visited[v]=0;/*置初值*/InitQueue(Q);z=LocateVex(G,start);/*先确定起点start在无向图中的位置*/for(v=0;v<G.vexnum;v++)if(!Visited[(v+z)%G.vexnum])/*v尚未访问*/{Visited[(v+z)%G.vexnum]=1;/*设置访问标志为TRUE(已访问)*/Visit(G.adjmulist[(v+z)%G.vexnum].data);EnQueue(Q,(v+z)%G.vexnum);while(!QueueEmpty(Q))/*队列不空*/ { DeQueue(Q,u); for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data)) if(!Visited[w]) { Visited[w]=1; Visit(G.adjmulist[w].data); EnQueue(Q,w); } }}DestroyQueue(Q);/*销毁队列,释放其占用空间*/}2、栈类型#defineSTACK_INIT_SIZE100/*存储空间初始分量*/#defineSTACKINCREMENT10/*存储空间分派增量*/typedefintSElemType;typedefstruct{SElemType*base;SElemType*top;/*栈顶指针*/intstacksize;}SqStack;栈的基本操作如下：StatusInitStack(SqStack&S)；//构造一种空栈S。StatusDestroyStack(SqStack&S)；//销毁栈S(无论空否均可)。StatusPush(SqStack&S,SElemTypee)；//在S的栈顶插入新的栈顶元素e。StatusPop(SqStack&S,SElemType&e)；//删除S的栈顶元素并以e带回其值。StatusStackEmpty(SqStackS)；//若S为空栈，则返回TRUE，否则返回FALSE。3、队列类型typedefintQelemType；typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;/*队头、队尾指针*/}LinkQueue;队列的基本操作如下：StatusInitQueue(LinkQueue&Q)；//构造一种空队列Q。StatusDestroyQueue(LinkQueue&Q)；//销毁队列Q(无论空否均可)。StatusQueueEmpty(LinkQueueQ)；//若Q为空队列,则返回1,否则返回-1。StatusEnQueue(LinkQueue&Q,QElemTypee)；//插入元素e为Q的新的队尾元素。StatusDeQueue(LinkQueue&Q,QElemType&e)；//若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回-1。4、生成树类型:typedefstructCSNode{VertexTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;/*树的二叉链表(孩子-兄弟)存储构造*/生成树的操作：voidDFSTree(AMLGraphG,intv,CSTree&DT)；//从第v个顶点出发深度遍历图G,建立以DT为根的生成树。voidDFSForest(AMLGraphG,VertexTypestart,CSTree&DT)；//建立图G的深度优先生成森林的(最左)孩子(右)兄弟链表DT。voidPrintTraverse(CSTreeT)；//打印图G的遍历生成树的边。voidPrintAllTraverse(CSTreeT)//打印图G的遍历生成森林的边。voidBFSTree(AMLGraphG,intv,CSTree&BT)；//从第v个顶点出发广度遍历图G,建立以BT为根的生成树。voidBFSForest(AMLGraphG,VertexTypestart,CSTree&BT)；//建立图G的广度优先生成森林的(最左)孩子(右)兄弟链表BT。voidPrintCSTree(CSTreeT,inti)；//用凹入表方式打印一棵以孩子-兄弟链表为存储构造的树。voidPrintCSForest(CSTreeT)；//用凹入表方式打印一棵以孩子-兄弟链表为存储构造的森林。其中部分操作的伪码算法如下：voidDFSTree(AMLGraphG,intv,CSTree&DT){/*从第v个顶点出发深度遍历图G,建立以DT为根的生成树*/first=1;Visited[v]=1;for(w=FirstAdjVex(G,G.adjmulist[v].data);w>=0;w=NextAdjVex(G,G.adjmulist[v].data,G.adjmulist[w].data))if(!Visited[w]){p=(CSTree)malloc(sizeof(CSNode));/*分派孩子结点*/strcpy(p->data,G.adjmulist[w].data);p->firstchild=NULL;p->nextsibling=NULL;if(first)/*w是v的第一种未被访问的邻接顶点是根的左孩子结点*/ { DT->firstchild=p; first=0; }else/*w是v的其他未被访问的邻接顶点是上一邻接顶点的右兄弟结点*/ q->nextsibling=p;q=p;DFSTree(G,w,q);/*从第w个顶点出发深度优先遍历图G,建立子生成树q*/}}voidBFSTree(AMLGraphG,intv,CSTree&BT){/*从第v个顶点出发广度遍历图G,建立以BT为根的生成树*/r=BT;i=j=0;Visited[v]=1;InitQueue(Q);EnQueue(Q,v);/*先把第一种顶点入队列*/while(!QueueEmpty(Q)){first=1;DeQueue(Q,u);for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))if(!Visited[w]){Visited[w]=1;p=(CSTree)malloc(sizeof(CSNode));strcpy(p->data,G.adjmulist[w].data);p->firstchild=NULL;p->nextsibling=NULL;if(first)/*w是v的第一种未被访问的邻接顶点是根的左孩子结点*/ { r->firstchild=p; first=0; }else/*w是v的其他未被访问的邻接顶点是上一邻接顶点的右兄弟结点*/ q->nextsibling=p; cur[i++]=p;/*用一种数组指针保留生成树的根*/ q=p; EnQueue(Q,w); }r=cur[j++];/*回朔到上一棵生成树的根*/}DestroyQueue(Q);}voidPrintCSTree(CSTreeT,inti){/*用凹入表方式打印一棵以孩子-兄弟链表为存储构造的树*/for(j=1;j<=i;j++)cout<<ends<<ends;/*留出i个空格以体现层*/cout<<T->data<<endl;/*打印元素,换行*/for(p=T->firstchild;p;p=p->nextsibling)PrintCSTree(p,i+1);/*打印子树*/}voidPrintCSForest(CSTreeT){/*用凹入表方式打印一棵以孩子-兄弟链表为存储构造的森树*/for(p=T;p;p=p->nextsibling){cout<<"第"<<i++<<"个树:"<<endl;PrintCSTree(p,0);}}5、主程序和其他伪码算法voidmain(){显示菜单；输入功能选择键；switch(flag){case1:手动构造一种图；case2:从文献导入一种图；case3:显示图的信息；case4:进行深度优先遍历图；case5:进行广度优先遍历图；case6:保留图到一种文献；case7:寻找途径；case8:销毁图；case9:退出程序；}销毁图；}intVisited[MAX_VERTEX_NUM];/*访问标志数组(全局量)*/voidAllPath(AMLGraphG,VertexTypestart,VertexTypenopass,VertexTypeend,intk){/*寻找途径*/Path[k]=start;/*加入目前途径中*/l=LocateVex(G,nopass);u=LocateVex(G,start);Visited[u]=1;if(start==end)/*找到了一条简朴途径*/{cout<<Path[0];for(i=1;Path[i];i++)cout<<"->"<<Path[i];/*打印输出*/cout<<endl;}elsefor(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data)){if(w==l)continue;/*假如找到那个不想通过的点,就绕过它,相称不执行背面的语句*/if(!Visited[w]) { temp=G.adjmulist[w].data; AllPath(G,temp,nopass,end,k+1);/*继续寻找*/ }}Visited[u]=0;Path[k]=0;/*回溯*/}voidSaveGraph(AMLGraphG)/*保留图的信息*/{建立输出文献流对象outgraph；输入文献名fileName；outgraph.open(fileName,ios::out);连接文献,指定打开方式if(!outgraph)/*调用重载算符函数测试流*/{cerr<<"文献不能打开."<<endl;abort();}向流插入数据；outgraph.close();/*关闭文献*/}voidLoadGraph(AMLGraph&G){建立输入文献流对象ingraph；输入文献名fileName；if(!ingraph){cerr<<"文献不能打开."<<endl;abort();}向流输出数据；ingraph.close();/*关闭文献*/}visit(VertexTypev){/*输出结点*/cout<<v<<ends;returnOK;}voidmessage()/*菜单显示*/{cout<<"\n\t\t********************\n";cout<<"\t\t*\t1:手动构造一种图\t*\n";cout<<"\t\t*\t2:从文献导入一种图\t*\n";cout<<"\t\t*\t3:显示图的信息\t*\n";cout<<"\t\t*\t4:进行深度优先遍历图\t*\n";cout<<"\t\t*\t5:进行广度优先遍历图\t*\n";cout<<"\t\t*\t6:保留图到一种文献\t*\n";cout<<"\t\t*\t7:寻找途径\t*\n";cout<<"\t\t*\t8:销毁图\t*\n";cout<<"\t\t*\t9:退出程序\t\t*\n";cout<<"\t\t********************\n";}四、调试分析1、本程序以邻接多重表为存储构造。这个程序波及到图的生成和图的深度以及广度遍历,文献的保留和读取，尚有栈和队列的操作，此外尚有森林的生成和打印，途径的寻找。2、本程序不仅可以进行连通无向图的遍历，还可以进行非连通图的遍历。为了以便显示和理解，目前暂且用一种大写字母表达一种顶点。边还可以附加信息，但为了以便操作，暂且不输入信息。已经先把图的有关信息保留在了文本文档里，因此要测试时直接从文献导入，可以减少用手输入的麻烦，同步也可以减少输入的错误。3、由于构造图时，后输入的边是插在先输入的边的前面。因此在输入边时，可以按字母从大到小的次序输入。那么显示图的时候就可以按字母从小到大的次序显示。4、程序定义了一种二倍顶点长的数组寄存输入的边，以便程序可以把它保留到文献里。故花费了一定的内存空间。五、顾客手册1、本程序的运行环境DOS操作系统，GTraverse.exe2、选择操作1：程序就提醒分别输入无向图的顶点数，边数，边的信息，顶点和边的值：输入完毕后，程序提醒按任一键返回菜单：3、选择操作2：程序提醒输入一种存有图信息文献的途径去导入一种图：假如导入成功，它会显示导入成功，并提醒按任一键返回。4、选择操作3：程序显示图的顶点和边的信息。5、选择操作4：系统提醒输入遍历图的起始点，程序运行后，首先显示深度优先遍历的访问结点序列和生成树的边集。然后再提醒按任一键继续显示深度优先遍历的生成森林。6、选择操作5：系统提醒输入遍历图的起始点，程序运行后，首先显示广度优先遍历的访问结点序列和生成树的边集。然后再提醒按任一键继续显示广度优先遍历的生成森林。7、选择操作6：程序会提醒输入要寄存图信息的文献的途径：8、选择操作7：程序会提醒输入途径遍历的起点start，终点end，不想通过的点nopass。9、选择操作8：销毁一种图。10、选择操作9：退出程序。六、测试成果选择操作1，分别进行如下操作：请输入图的节点数(EG.G.vexnum=10):8请输入图的边数(EG.G.edgenum=4):9请输入8个节点的表达值:ABCDEFGH请输入有序的边(用空格作间隔):FGEHDHCGCFBEBDACAB2)选择操作3，输出图的信息如下：这个图有8叶子:ABCDEFGH这个图有9边:A-BA-CB-DB-EC-FC-GD-HE-HF-G3）选择操作4，输入遍历起点，如A（也可以输入B，C……）*****深度优先遍历图的成果*****深度优先遍历的访问结点序列:ACGFBEHD深度优先遍历生成树的边集:A-BB-DD-HH-EA-CC-FF-G深度优先遍历的生成森林:第1个树:ABDHECF