实现图的遍历算法实验报告

严蔚敏版数据结构图的遍历完整实验报告

实现图的遍历算法

1. 需求分析

对于下图G,编写一个程序输出从顶点0开始的深度优先遍历序列(非递归算法)和广度优先遍历序列(非递归算法)。

实现图的遍历算法实验报告

2. 系统设计

1.用到的抽象数据类型的定义

图的抽象数据类型定义:

ADT Graph{

数据对象V:V是具有相同特性的数据元素的集合,称为顶点集

数据关系R:

R={VR}

VR={<v,w>|v,w∈V且P(v,w),<v,w>表示从v到w的弧,

谓词P(v,w)定义了弧<v,w>的意义或信息}

基本操作P:

CreatGraph(&G,V,VR)

初始条件:V是图的顶点集,VR是图中弧的集合

操作结果:按V和VR的定义构造图G

DestroyGraph(&G)

初始条件:图G存在

操作结果:销毁图G

InsertVex(&G,v)

初始条件:图G存在,v和图中顶点有相同特征

操作结果:在图G中增添新顶点v

……

InsertArc(&G,v,w)

初始条件:图G存在,v和w是G中两个顶点

操作结果:在G中增添弧<v,w>,若G是无向的则还增添对称弧<w,v>

……

DFSTraverse(G,Visit())

初始条件:图G存在,Visit是顶点的应用函数

操作结果:对图进行深度优先遍历,在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败,则操作失败

你可能喜欢

  • 数据结构图的遍历实验报告
  • 算法设计与分析
  • 深度优先算法
  • 邻接矩阵
  • C语言课程设计通讯录

实现图的遍历算法实验报告相关文档

最新文档

返回顶部