资源描述：
《图遍历的演示.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构》课程实验报告题目：图遍历的演示班级：姓名：学号：专业：学院：完成日期：一、需求分析Word文档（1）问题描述：很多涉及图上操作的算法都是以图的遍历操作作为基础的。试写一个程序，演示在连通图的无向图上访问全部结点的操作。（2）基本要求：以邻接多重表（选作内容邻接表）为存储结构，实现连通无向图的深度优先遍历和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集（3）输入的形式和输入的范围：先输入顶点数N以及边数M，然后依次输入N个顶点，再按提示输入M条边的信息用（a-b3）类似的形式（4）测试数据：教科书图7.33部分信息二
2、、概要设计（1）抽象数据类型图的定义：ADTGraph{数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。数据关系R:R=｛VR｝VR={
3、v,wєV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作P：locatevex(G,mes)；初始条件：图G存在，mes和G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。createudn(&G)；初始条件：图G存在。操作结果：创建无向图。createdn(&G)；初始条件：图G存在。操作结果：创建有向图。crea
4、teudg(&G)；初始条件：图G存在操作结果：创建无向网。createdg(&G)；初始条件：图G存在。操作结果：创建有向网。DFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：深度优先搜索遍历图G，访问顶点时使用函数visit.BFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：广度优先搜索遍历图G，访问顶点时使用函数Word文档visit.visit(a)；初始条件：a为图中的某个顶点值。操作结果：访问顶点a，本程序中作用结果为输出顶点值。｝ADTGraph（2）.邻接表存储结构的图定义：A
5、DTalgraph{数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。数据关系R:R=｛VR｝VR={
6、v,wєV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作P：locatevex(G,mes)；初始条件：图G存在，mes和G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。createudn(&G)；初始条件：图G存在。操作结果：创建无向图。createdn(&G)；初始条件：图G存在。操作结果：创建有向图。Createudg(&G)；初始条件：图G存
7、在。操作结果：创建无向网。createdg(&G)；初始条件：图G存在。操作结果：创建有向网。DFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：深度优先搜索遍历图G，访问顶点时使用函数visit.BFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：广度优先搜索遍历图G，访问顶点时使用函数visit.visit(a)；初始条件：a为图中的某个顶点值。操作结果：访问顶点a，本程序中作用结果为输出顶点值。｝ADTalgraph2.（3）设定队列的抽象数据类型定义：ADTQueue{数据对象：D={ai
8、
9、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={
10、ai-1,ai∈D,i=1,2,…,n}约定a1为队列头，an为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。Word文档DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：销毁队列Q。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的
11、数据元素个数，即队列的长度。GetHead(Q,&e)初始条件：队列Q已存在且非空。操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)初始条件：队列Q已存在且非空。操作结果：删除Q的队头元素，并用e返回其值。QueueTraverse(Q,visit())初始条件：队列Q已存在且非空。操作结果：从队头到队尾依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。}ADTQueue三、详细设计（1）元素类型、结点类型和指针类型t
