1、数据结构课程设计 图的遍历 1 图遍历的演示 题目题目: :很多涉及图上操作的算法都是以图的遍历操作为基础的。很多涉及图上操作的算法都是以图的遍历操作为基础的。试设计一个程序,演示在连 通和非连通的无向图上访问全部结点的操作 一、需求分析一、需求分析 1、以邻接多重表为存储结构； 2、实现连通和非连通的无向图的深度优先和广度优先遍历； 3、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集； 二、二、概要设计概要设计 1、设定图的抽象数据类型: ADTADT Graph 数据对象数据对象 V V:V 是具有相同特性的数据元素的集合,称为点集. 数据关系数据关系 R R: R
2、=VR VR=(v,w)|v,w 属于 V,(v,w)表示 v 和 w 之间存在的路径 基本操作基本操作 P:P: CreatGraph(否则返回其他信息 GetVex(G,v) 初始条件: 图 G 存在,v 是 G 中顶点 操作结果:返回 v 的值 FirstAjvex(G,v) 初始条件: 图 G 存在,v 是 G 中顶点 操作结果:返回 v 的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空 NextAjvex(G,v,w) 初始条件: 图 G 存在,v 是 G 中顶点,w 是 v 的邻接顶点 操作结果:返回 v 的下一个邻接顶点,若 w 是 v 的最后一个邻接顶点,则返回空 Dele
3、teVexx( 初始条件：栈 S 已存在。 操作结果：在栈 S 的栈顶插入新的栈顶元素 e。 Pop( 初始条件：栈 S 已存在。 操作结果：删除 S 的栈顶元素，并以 e 返回其值。 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若 S 为空栈，则返回 TRUE，否则返回 FALSE。 ADT Stack 3、设定队列的抽象数据类型： ADTADT Queue 数据对象数据对象: :D=ai|ai 属于 Elemset,i=1,2.,n,n=0 数据关系数据关系:R1=|ai-1,ai 属于 D,i=1,2,n 约定 ai 为端为队列头,an 为队列尾 基本操作基本操作:
4、 : InitQueue( /*相关信息类型*/ typedef char VertexType; /* 字符类型 */ typedef enumunvisited,visitedVisitIf; typedef struct EBox VisitIf mark; /* 访问标记 */ int ivex,jvex; /* 该边依附的两个顶点的位置 */ struct EBox *ilink,*jlink; /* 分别指向依附这两个顶点的下一条边 */ InfoType *info; /* 该边信息指针 */ EBox; typedef struct VertexType data; EBox *firstedge; /* 指向第一条依附该顶点的边 */ VexBox; typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum,edgenum; /* 无向图的当前顶点数和边数 */ AMLGr
