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

实现图的遍历算法实验报告一实验题目: 实现图的遍历算法二实验要求: : (1) 建立如图( p126 ) 所示的有向图 G 的邻接矩阵, 并输出之(2) 由有向图 G 的邻接矩阵产生邻接表,并输出之(3) 再由( 2 )的邻接表产生对应的邻接矩阵,并输出之 (1 )输出如图 所示的有向图 G 从顶点 0 开始的深度优先遍历序列(递归算法) (2) 输出如图 所示的有向图 G 从顶点 0 开始的深度优先遍历序列(非递归算法) (3) 输出如图 所示的有向图 G 从顶点 0 开始的广度优先遍历序列三实验内容: 图的抽象数据类型: 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> 的意义或信息} 基本操作: CreateGraph( &G, V, VR ) 初始条件: V 是图的顶点集, VR 是图中弧的集合。操作结果:按 V和 VR 的定义构造图 G。 DestroyGraph( &G ) 初始条件:图 G 存在。操作结果:销毁图 G。 LocateVex( G,u) 初始条件:图 G 存在, u和G 中顶点有相同特征。操作结果:若G 中存在顶点 u, 则返回该顶点在图中位置; 否则返回其它信息。 GetVex( G,v) 初始条件:图 G 存在, v是G 中某个顶点。操作结果:返回 v 的值。 PutVex( &G, v, value ) 初始条件:图 G 存在, v是G 中某个顶点。操作结果:对 v 赋值 value 。 FirstAdjVex( G,v) 初始条件:图 G 存在, v是G 中某个顶点。操作结果:返回 v 的第一个邻接顶点。若顶点在 G 中没有邻接顶点,则返回“空”。 NextAdjVex( G, v,w) 初始条件:图 G 存在, v是G 中某个顶点, w是v 的邻接顶点。操作结果: 返回 v的( 相对于 w的) 下一个邻接顶点。若w是v 的最后一个邻接点,则返回“空”。 InsertVex( &G, v) 初始条件:图 G 存在, v 和图中顶点有相同特征。操作结果:在图 G 中增添新顶点 v。 DeleteVex( &G, v) 初始条件:图 G 存在, v是G 中某个顶点。操作结果:删除 G 中顶点 v 及其相关的弧。 InsertArc( &G, v,w) 初始条件:图 G 存在, v和w是G 中两个顶点。操作结果:在G 中增添弧<v,w> ,若G 是无向的, 则还增添对称弧<v,w> 。 DeleteArc( &G, v,w) 初始条件:图 G 存在, v和w是G 中两个顶点。操作结果:在G 中删除弧<v,w> ,若G 是无向的, 则还删除对称弧<v,w> 。 DFSTraverse( G, Visit() ) 初始条件:图 G 存在, Visit 是顶点的应用函数。操作结果: 对图进行深度优先遍历。在遍历过程中对每个顶点调用函数 Visit 一次且仅一次。一旦 visit() 失败,则操作失败。 BFSTraverse( G, Visit() ) 初始条件:图 G 存在, Visit 是顶点的应用函数。操作结果: 对图进行广度优先遍历。在遍历过程中对每个顶点调用函数 Visit 一次且仅一次。一旦 visit() 失败,则操作失败。}ADT Graph 存储结构的定义; #define maxx 100 #define inf 32767 int vis[maxx]={0}; /// 邻接矩阵 typedef struct { int no; /// 顶点编号 int info; } VertexType; /// 顶点类型 typedef struct { int edges[maxx][maxx]; int n, e; VertexType vexs[maxx]; } MGraph; /// 邻接表 typedef struct ANode /// 边的结构定义{ int adjvex; /// 边的终点位置 struct ANode *nextarc; /// 指向下一条边的指针 int info; /// 权值} ode; typedef struct Vnode /// 表头定义{ int data; /// 顶点信息 ode *firstarc; /// 指向第一条边}VNode; typedef VNode AdjList[maxx]; typedef struct { AdjList adjlist; /// 邻接表 int n,