数据结构实验五(图的遍历).doc

《数据结构实验五(图的遍历).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验五实验报告实验名称：图的遍历姓名：黄州龙班级：08软件工程A班学号：0825121022一、需求分析1、本实验要求要利用图论的一些基本概念和算法来实现对无向图和有向图的2种遍历，分别是深度优先遍历(DFS)和广度优先遍历(BFS)，通过本实验对图遍历算法的实现来帮助了解图这一特殊(多对多)的数据结构，以便在以后的实际应用中可以以此为基础来进行更好的软件程序开发；2、该程序开始时是通过用户输入的图的数据文件(.txt)所在的路径来读取对应文件中的图的数据，以此来构建，进而调用遍历算法函数来对图进行遍历，如果

2、文件不存在或路径不正确，程序将会报告错误并终止；3、本程序读取的文件的格式是.txt文件，其中存储的数据组成如下:第一行:MN，M是图中结点的个数，N是图中弧的条数第二行:D，D是1或0,1表示该图是一个有向图，0表示该图是一个无向图第三行:M个互不相同的字符，代表每个结点的字符数据接下来的N行，每行有2个字母P1、P2，对于有向图，表示存在一条从P1到P2的有向边；对于无向图，表示在P1和P2之间存在一条边；1、程序中采用的图的存储结构为邻接表，对于有向图，一条弧将存储一个弧结点，对于无向图，一条弧将存储两条弧结点

3、;2、测试数据：（1）、Graph1.txt891ABCDEFGHABACBDBECFCGEHGFHD（2）Graph2.txt761ABCDEFGACBACBDEDFE（3）Graph3.txt980ABCDEFGHIABBCBHDHEHFHGHIH（4）Graph4.txt11120ABCDEFGHIJKABADBCCDEJEKFGFKGHHKIJIK一、概要设计1、图的邻接表的定义structArcNode//弧结点的定义{intadjvex;//邻接点的位置ArcNode*nextarc;//下一条弧};st

4、ructVNode//顶点结点的定义{chardata;//该顶点的数据域，这里简化为一个字符boolvisited;//是否被访问的标志域，0未访问，1已访问ArcNode*firstarc;//指向第一条以该顶点为出发点的弧//的指针域};structAlGraph//定义邻接表表示的图的数据结构{VNodevexs[MAXSIZE];//顶点向量intarcnum;//弧的数目intvexnum;//顶点的数目boolisDirected;//是否为有向图的标志域,1为有向，0为无//向};1、图的邻接表创建模

5、块StatuscreateAlGraph(AlGraph&g,stringfile)初始条件:file所指文件路径是正确的参数:g传入要创建的邻接表，file传入图的数据所在文件操作结果:创建一个邻接表intlocateVex(AlGraphg,charvexdata)初始条件:邻接表g已经初始化参数:g传入图的邻接表，vexdata传入顶点字符数据，操作结果:返回所查询顶点在邻接表的顶点向量中的位置，若查询失败，返回-1StatusaddArc(AlGraph&g,intfrom,intto)初始条件:邻接表g已经

6、初始化，from所指顶点位置合法，to所指顶点位置合法参数:g传入图的邻接表，from传入起点的位置，to传入终点的位置操作结果:在邻接表中添加一条弧，如果是双向图，将通过添加2条弧来表示无向边3、深度优先遍历和广度优先遍历模块voidDFS(AlGraph&g,intv,vector&edges)初始条件:g已经初始化，v所指顶点位置存在参数:g传入图的邻接表，v传入深度优先搜索的起点位置，edges传入用来存储生成树的边的向量操作结果:从v位置的顶点递归地深度优先搜索图voidDFSVisit(AlG

7、raph&g,int&count)初始条件:g已经初始化参数:g传入图的邻接表，count传入深度优先搜索使用的次数计数器操作结果:对整个图进行深度优先遍历voidBFS(AlGraph&g,intv,vector&edges)初始条件:g已经初始化，v所指顶点位置存在参数:g传入图的邻接表，v传入广度优先搜索的起点位置edges传入用来存储生成树边的向量操作结果:从v位置的顶点递归地广度优先搜索图voidBFSVisit(AlGraph&g,int&count)初始条件:g已经初始化参数:g传入图的邻接

8、表，count传入广度优先搜索使用的次数计数器操作结果:对整个图进行广度优先遍历一、详细设计1、图的邻接表创建模块StatuscreateAlGraph(AlGraph&g,stringfile){ifstreamis(file.c_str());is>>g.vexnum>>g.arcnum;//读入定点数和弧的数目intisDirected=