图的遍历实验报告.doc

图的遍历实验报告

实验4:图的遍历主题:

图及其应用——图的遍历类；

姓名:

学生编号:

完成日期:

一、需求分析1。问题描述:

许多涉及图操作的算法都是基于图遍历操作的。试着写一个程序来演示访问连通无向图上所有节点的操作。2.基本要求:

邻接表作为存储结构，实现了连通无向图的深度优先和广度优先遍历。从用户指定的节点开始，分别输出每次遍历下的节点访问顺序和相应生成树的边集。3.测试数据:

教科书中的图7.33。暂时忽略里程，从北京开始。4.实施提示: 假设一个图不超过30个节点，每个节点用一个数字表示(如果一个图有n个节点，它们的数字是1，2，分别为n)。通过将一个图的所有边输入到一个图中，每个边是一对，边的输入顺序可以被限制。请注意，生成树的边是有向边，端点的顺序不能颠倒。5.选定内容:

(1)。借助堆栈类型(自行定义和实现)，使用非递归算法实现深度优先遍历。(2)以邻接表为存储结构，建立深度优先生成树和广度优先生成树，然后根据凹表或树打印生成树。为了实现上述功能，需要图形的抽象数据类型。抽象数据类型定义为:

ADT图{数据对象v:

v是一组具有相同特征的数据元素，称为顶点集。数据关系r:

R={VR} VR={ | v，wv和P(v，w)，表示从v到w的弧，谓词P(v，w)定义弧的含义或信息}} ADT图2。该抽象数据类型中的一些常量如下:

#定义true1 #定义false 0 #定义ok 1 #定义max _ n 20//最大顶点数typedef char顶点类型[20]；typedef枚举{DG，DN，AG，AN}图形种类；枚举BOOL {假，真}；3.树的结构类型如下:

Typedef结构{//圆弧节点和矩阵的int类型调整；//VRType是弧的类型。图的遍历主题——图；

图及其应用——图的遍历类；

姓名:

学生编号:

完成日期:

一、需求分析1。问题描述:

许多涉及图操作的算法都是基于图遍历操作的。试着写一个程序来演示访问连通无向图上所有节点的操作。2.基本要求:

邻接表作为存储结构，实现了连通无向图的深度优先和广度优先遍历。从用户指定的节点开始，分别输出每次遍历下的节点访问顺序和相应生成树的边集。3.测试数据:

教科书中的图7.33。暂时忽略里程，从北京开始。4.实施提示: 假设一个图不超过30个节点，每个节点用一个数字表示(如果一

个图有n个节点，它们的数字是1，2，分别为n)。通过将一个图的所有边输入到一个图中，每个边是一对，边的输入顺序可以被限制。请注意，生成树的边是有向边，端点的顺序不能颠倒。5.选定内容:

(1)。借助堆栈类型(自行定义和实现)，使用非递归算法实现深度优先遍历。(2)以邻接表为存储结构，建立深度优先生成树和广度优先生成树，然后根据凹表或树打印生成树。为了实现上述功能，需要图形的抽象数据类型。抽象数据类型定义为:

ADT图{数据对象v:

v是一组具有相同特征的数据元素，称为顶点集。数据关系r:

R={VR} VR={ | v，wv和P(v，w)，表示从v到w的弧，谓词P(v，w)定义弧的含义或信息}} ADT图2。该抽象数据类型中的一些常量如下:

#定义true1 #定义false 0 #定义ok 1 #定义max _ n 20//最大顶点数typedef char顶点类型[20]；typedef枚举{DG，DN，AG，AN}图形种类；枚举BOOL {假，真}；3.树的结构类型如下:

Typedef结构{//圆弧节点和矩阵的int类型调整；//VRType是弧的类型。图:主程序模块树模块遍历模块三。详细设计#包括-省略部分-没有相邻点，之后返回；//返回第一个非0元下标后的第五行和第五列}int访问[100]；/*设置全局访问标志数组*/void DFS(图G，int v) {//从序号为v的顶点开始，对图G进行深度优先搜索，遍历int w；参观[v]=1；cout=0；w=NextAdjVex(G，v，w)) { if(！访问了[西部)；} }//深度优先搜索遍历图Gvoid数据流(MgRaph G){ int v；对于(v=0；Exe

2。进入演示程序后，用户界面以真实文本模式显示:

6.将测试结果依次输入到单词模型div中；㈤[五世]