图遍历的演示实习报告

数据结构课程设计图的遍历1图遍历的演示题目:试设计一个程序,演示在连通和非连通的无向图上访问全部结点的操作班级：07级计科院网络工程姓名：刘振帮学号：07066017完成日期：一、需求分析1、以邻接多重表为存储结构；2、实现连通和非连通的无向图的深度优先和广度优先遍历；3、要求利用栈实现无向图的广度和深度优先遍历；4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集；5、用凹入表打印生成树；6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径；6、本程序用C++语言编写，在TURBOC++3.0环境下通过。二、概要设计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())数据结构课程设计图的遍历2初始条件:图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返回其值数据结构课程设计图的遍历3QueueEmpty(Q)初始条件:队列已经存在操作结果:若队列为空,则返回TRUE,否则返回FLASE}ADTQueue4、本程序包含九个模块：1）主程序模块voidmain(){手动构造一个图；从文件导入一个图；显示图的信息；进行深度优先遍历图；进行广度优先遍历图；保存图到一个文件；寻找路径；销毁一个图；}；2）手动构造一个图-自己输入图的顶点和边生成一个图；3）从文件导入一个图；4）显示图的信息-打印图的所有顶点和边；5）进行深度优先遍历图-打出遍历的结点序列和边集；6）进行广度优先遍历图-打出遍历的结点序列和边集；7）保存图到一个文件；8）寻找从起点到终点，但中间不经过某点的所有简单路径；9）销毁图。三、详细设计1、顶点,边和图类型#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;数据结构课程设计图的遍历4typedefstruct{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;kG.edgenum;++k)/*构造表结点链表*/{读入两个顶点va、vb；i=LocateVex(G,va);/*一端*/j=LocateVex(G,vb);/*另一端*/数据结构课程设计图的遍历5p=(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;iG.vexnum;i++){p=G.adjmulist[i].firstedge;while(p)if(p-ivex==i)/*边的i端与该顶点有关*/{if(!p-mark)/*只输出一次*/{coutG.adjmulist[i].data'-'G.adjmulist[p-jvex].dataends;p-mark=visited;}p=p-ilink;}else/*边的j端与该顶点有关*/{if(!p-mark)/*只输出一次*/{coutG.adjmulist[p-ivex].data'-'G.adjmulist[i].dataends;p-mark=visited;}p=p-jlink;}coutendl;}}voidDFSTraverse(AMLGraphG,VertexTypestart,int(*visit)(VertexType)){/*从start顶点起,深度优先遍历图G(非递归算法)*/InitStack(S);w=LocateVex(G,start);/*先确定起点start在无向图中的位置*/数据结构课程设计图的遍历6for(v=0;vG.vexnum;v++)Visited[v]=0;/*置初值*/for(v=0;vG.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;vG.vexnum;v++)Visited[v]=0;/*置初值*/InitQueue(Q);z=LocateVex(G,start);/*先确定起点start在无向图中的位置*/for(v=0;vG.vexnum;v++)if(!Visited[(v+z)%G.vexnum])/*v尚未访问*/{Visited[(v+z)%G.vexnum]=1;/*设置访问标志为TRUE(已访问)*/Visit(G.adjmulist[(v+z)%G.vexnum].da