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

下载本文档

阅读 181
下载 22
格式 pdf
大小 293.41 KB
约11页
2025-02-18 发布于天津市
收藏
评论
点赞(0)
海报
举报

1/11页

2/11页

3/11页

在线预览已结束，请下载后查看完整版，加入VIP享文档下载特权

/11

文本预览下载提示常见问题

实现图的遍历算法 1．需求分析对于下图G，编写一个程序输出从顶点0 开始的深度优先遍历序列（非递归算法）和广度优先遍历序列（非递归算法）。 2．系统设计 1．用到的抽象数据类型的定义图的抽象数据类型定义： ADT Graph{ 数据对象V：V 是具有相同特性的数据元素的集合，称为顶点集数据关系R： R={VR} VR={|v,w∈V 且P(v,w),表示从v 到w 的弧，谓词P(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 中增添弧，若 G 是无向的则还增添对称弧 …… DFSTraverse(G,Visit()) 初始条件：图G 存在，Visit 是顶点的应用函数操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦 Visit()失败，则操作失败 BFSTraverse(G,Visit()) 初始条件：图G 存在，Visit 是顶点的应用函数操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦Visit()失败，则操作失败 }ADT Graph 栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={|ai-1,ai∈D,i=2,…,n} 约定an 端为栈顶，ai 端为栈底基本操作： InitStack(&S) 操作结果：构造一个空栈S DestroyStack(&S) 初始条件：栈S 已存在操作结果：将 S 清为空栈 StackEmpty(S) 初始条件：栈S 已存在操作结果：若栈S 为空栈，则返回 TRUE，否则FALSE …… Push(&S,e) 初始条件：栈S 已存在操作结果：插入元素 e 为新的栈顶元素 Pop(&S,&e) 初始条件：栈S 已存在且非空操作结果：删除 S 的栈顶元素，并用e 返回其值 StackTraverse(S,visit()) 初始条件：栈S 已存在且非空操作结果：从栈底到栈顶依次对S 的每个数据元素调用函数visit()，一旦visit()失败，则操作失效 }ADT Stack 队列的抽象数据类型定义： ADT Queue{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：Rl={|ai-1,a...

1、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
3、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。

碎片内容