数据结构—图的遍历报告

《数据结构—图的遍历报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、软件学院的遍历实验报告课程名称:

2、Z/:据结核姓名：趣涎学号：201370034217班级:卓越131实验五的基本操作一、实验目的1、使学生可以巩固所学的有关图的基木知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容木次实验提供4个题目，难度相当，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！题目一：图的遍历（必做〉［问题描述］对给定图，实现图的深度优先遍历和广度优先遍历。［基本要求］以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】由学

3、生依据软件工程的测试技术自己确定。题目二：在图G中求一条从顶点i到顶点s的简单路径［测试数据］自行设计［题目三］:在图G中求一条从顶点i到顶点s且长度为K的简单路径［测试数据］自行设计三、算法设计1)创建邻接表函数：voidCreateGraph(ALGraph&G);2)广度遍历邻接表函数：voidBFSTraverse(ALGraphG,int(*Visit)(intv))3)深度遍历邻接表函数：voidDFSTraverse(ALGraphG,int(*Visit)(intv))4)voidDFS(ALGraphG,intv)5)intFirstA

4、djVex(ALGraphG,intv)6)intNextAdjVex(ALGraphG,intv,intw)7)初始化队列函数：intInitQueue(SqQueue&queue)8)入队列函数：intEnQueue(SqQueue&queue,intelement)9)出队列函数：intDeQueue(SqQueue&queue,int&element)10)判断队列是否为空函数：intQueueEmpty(SqQueuequeue)11）访问打印结点函数：intprintGraph（intv）实验结果五、总结通过做图的遍历实验让对最优图这种结构有

5、了更深的丫解和应用，对我以后的编程产生了比较深远的影响。六、源程序（带注释）#include#include#include#include#defineMAX_VERTEX_NUM20#defineMAXQSIZE10usingnamespacestd;typedefintVertexType;typedefstruct{int*base;intfront;intrear;JSqQueue;typedefstructArcNode{intadjvex;structArcNod

6、e*nextarc;}ArcNode;typedefstructVNode{intdata;ArcNode*firstare;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arenum;JALGraph;boolvisited[MAX_VERTEX_NUM];intw;int(*VisitFunc)(intv);voidCreateGraph(ALGraph&G);voidDFSTraverse(ALGraphG,int(*Visit)(intv));void

7、DFS(ALGraphG,intv);voidBFSTraverse(ALGraphG,int(*Visit)(intv));intprintGraph(intv);intFirstAdjVex(ALGraphG,intv);intNextAdjVex(ALGraphG,intv，intw);intInitQueue(SqQueue&);intEnQueue(SqQueue&，int);intDeQueue(SqQueue&，int&);intQueueEmpty(SqQueue);intmain()inti;ALGraphG;ArcNode*p;cou

8、t«n*图的遍历*"«endl;CreateGraph(G);cout«endl;cout«”输入邻接表如下:"《endl;for(i=0;iu;cout«(p->adjvex);p=p-〉nextarc;}cout«endl;}cout«"深搜DFSTraverse(G,printGraph);cout«endl;cout«"广搜->n;BFSTraverse(G,pri

9、ntGraph);cout«endl;return0;}//创建邻接表voidC