实现图的邻接矩阵和邻接表存储 1. 需求分析 对于下图所示的有向图G,编写一个程序完成如下功能: 1. 建立G 的邻接矩阵并输出之 2. 由G 的邻接矩阵产生邻接表并输出之 3. 再由2 的邻接表产生对应的邻接矩阵并输出之 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 2. 主程序的流程: 调用CreateMG 函数创建邻接矩阵 M; 调用PrintMatrix 函数输出邻接矩阵 M 调用CreateMGtoDN 函数,由邻接矩阵 M 创建邻接表 G 调用PrintDN 函数输出邻接表 G 调用CreateDNtoMG 函数,由邻接表 M 创建邻接矩阵 N 调用PrintMatrix 函数输出邻接矩阵 N 3.函数关系调用图: 3.调试分析 (1)在MGraph 的定义中有枚举类型 typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网} 赋值语句 G.kind(int)=M.kind(GraphKind);是正确的,而反过来 M.kind=G.kind 则是错误的, 要加上那个强制转换 M.kind=GraphKind(G.kind);枚举类型 enum{DG,DN,UDG,UDN} 会自动赋值 DG=0;DN=1,UDG=2,UDN=3;可以自动从 GraphKind 类型转换到 int 型,但不会自动从 int 型转换到 GraphKind 类型 (2)算法的时间复杂度分析: CreateMG、CreateMGtoDN、Cre...