资源描述：
《实现图的遍历算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实现图的遍历算法1．需求分析对于下图G，编写一个程序输出从顶点0开始的深度优先遍历序列（非递归算法）和广度优先遍历序列（非递归算法）。2．系统设计1．用到的抽象数据类型的定义图的抽象数据类型定义：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集数据关系R：R={VR}VR={
2、v,w∈V且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作P：CreatGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合操作结果
3、：按V和VR的定义构造图GDestroyGraph(&G)初始条件：图G存在操作结果：销毁图GInsertVex(&G,v)初始条件：图G存在，v和图中顶点有相同特征操作结果：在图G中增添新顶点v……InsertArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点操作结果：在G中增添弧，若G是无向的则还增添对称弧……DFSTraverse(G,Visit())初始条件：图G存在，Visit是顶点的应用函数操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅
4、一次。一旦Visit()失败，则操作失败BFSTraverse(G,Visit())初始条件：图G存在，Visit是顶点的应用函数操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败}ADTGraph栈的抽象数据类型定义：ADTStack{数据对象：D={ai
5、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={
6、ai-1,ai∈D,i=2,…,n}约定an端为栈顶，ai端为栈底基本操作：InitStack(&S
7、)操作结果：构造一个空栈SDestroyStack(&S)初始条件：栈S已存在操作结果：将S清为空栈StackEmpty(S)初始条件：栈S已存在操作结果：若栈S为空栈，则返回TRUE，否则FALSE……Push(&S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值StackTraverse(S,visit())初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()，一旦vis
8、it()失败，则操作失效}ADTStack队列的抽象数据类型定义：ADTQueue{数据对象：D={ai
9、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：Rl={
10、ai-1,ai∈D,i=2,…,n}约定其中ai端为队列头，an端为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列QDestroyQueue(&Q)初始条件：队列Q已存在操作结果：队列Q被销毁，不再存在QueueEmpty(Q)初始条件：队列Q已存在操作结果：若Q为空队列，则返回TRUE，否则FALS
11、E……EnQueue(&Q,e)初始条件：队列Q已存在操作结果：插入元素e为Q的新的队尾元素DeQueue(&Q,&e)初始条件：Q为非空队列操作结果：删除Q的队头元素，并用e返回其值}ADTQueue2．主程序的流程：调用CreateDN函数创建图的邻接表G；调用PrintDN函数输出邻接表G；调用DFSTraverse函数深度优先遍历图；调用BFSTraverse函数广度优先遍历图3．函数关系调用图：LocateVexmainVisitFirstAdjVexCreateDNNextAdjVexInitStac
12、kPrintDNInitQueueStackEmptyEnQueueGetTopDFSTraverseQueueEmptyPushBFSTraverseDeQueuePop主程序3．调试分析（1）书上给出了图的广度优先非递归遍历算法，主要是要实现里面的FirstAdjVex(G,u)和NextAdjVex(G,u,w)函数。我刚开始编写的这两个函数分别为：intFirstAdjVex(ALGraphG,intu){returnLocateVex(G,G.vertices[u].firstarc->adjvex);
13、}intNextAdjVex(ALGraphG,intu,intw){ArcNode*p=G.vertices[u].firstarc;while(LocateVex(G,p->adjvex)!=w)p=p->nextarc;p=p->nextarc;if(!p)return-1;returnLocateVex(G,p->adjvex);}对于书上给出的BFSTraver
