数据结构图的遍历实验报告.doc

《数据结构图的遍历实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、题目：图的遍历的实现完成日期：2011.12.22一、需求分析1.本演示程序中，输入的数据类型均为整型数据，不允许输入字符等其他数据类型，且需要按照提示内容进行输入，成对的关系数据必须在所建立的图中已经存在对应的结点。2.演示程序以用户和计算机的对话方式执行，在计算机终端上显示的提示信息的说明下，按照要求输入数据，运算结果在其后显示。3.本程序实现分别基于邻接矩阵和邻接表存储结构的有、无向图，有、无向网的建立和遍历。遍历分DFS和BFS两种算法，并分别以递归和非递归形式实现。4.测试数据：（1）无向图结点数4弧数3结点：

2、1234结点关系：12；13；24（2）有向图结点数6弧数6结点：123456结点关系：12；13；24；35；36；25二、概要设计为实现上述程序功能，图的存储结构分为邻接矩阵和邻接表两种。遍历过程中借助了栈和队列的存储结构。1.邻接矩阵存储结构的图定义：ADTmgraph{数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。数据关系R:R=｛VR｝VR={

3、v,wєV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作P：locatevex(G,mes

4、)；初始条件：图G存在，mes和G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。createudn(&G)；初始条件：图G存在。操作结果：创建无向图。createdn(&G)；初始条件：图G存在。操作结果：创建有向图。createudg(&G)；初始条件：图G存在。23操作结果：创建无向网。createdg(&G)；初始条件：图G存在。操作结果：创建有向网。DFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：深度优先搜索遍历图G，访问顶点时使

5、用函数visit.BFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：广度优先搜索遍历图G，访问顶点时使用函数visit.visit(a)；初始条件：a为图中的某个顶点值。操作结果：访问顶点a，本程序中作用结果为输出顶点值。｝ADTmgraph1.邻接表存储结构的图定义：ADTalgraph{数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。数据关系R:R=｛VR｝VR={

6、v,wєV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意

7、义或信息}基本操作P：locatevex(G,mes)；初始条件：图G存在，mes和G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。createudn(&G)；初始条件：图G存在。操作结果：创建无向图。createdn(&G)；初始条件：图G存在。操作结果：创建有向图。createudg(&G)；初始条件：图G存在。操作结果：创建无向网。createdg(&G)；初始条件：图G存在。操作结果：创建有向网。DFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐

8、标。操作结果：深度优先搜索遍历图G，访问顶点时使用函数visit.BFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：广度优先搜索遍历图G，访问顶点时使用函数visit.23visit(a)；初始条件：a为图中的某个顶点值。操作结果：访问顶点a，本程序中作用结果为输出顶点值。｝ADTalgraph1.主程序流程：定义并创建图statuscreatgraph(mgraph&G){cout<<"请选择构造的图的类型：（1:有向图，2:有向网，3:无向图，4:无向网）"<

9、ind;scanf("%d",&kind);switch(kind)//通过选择确定创建哪一种图；{case1:returncreatedg(G);case2:returncreatedn(G);case3:returncreateudg(G);case4:returncreateudn(G);default:returnerror;}}然后采用DFS或BFS进行遍历（访问结果为输出顶点值）。4.函数的调用关系图：maincreatgraphDFS(BFS)createdgcreatedncreateudgcreateu

10、dnvisitinitstackpushdestroystacklocatevexpopgettopvisitlocatevexlinkqueueenqueuegetheaddequeuedestroyqueue其中，当DFS使用递归算法时相关的栈操作不使用，当BFS使用递归算法时相关的队列操作仍有部分使用。23四、