欢迎来到天天文库
浏览记录
ID:22291217
大小:231.94 KB
页数:9页
时间:2018-10-28
《数据结构—图的遍历报告》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
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
此文档下载收益归作者所有