数据结构实验-图的基本操作

浙江大学城市学院实验报告浙江大学城市学院实验报告 课程名称课程名称 数据结构 实验项目名称实验项目名称 实验十三 十四 图的基本操作 学生姓名学生姓名 专业班级专业班级 学号学号 实验成绩实验成绩 指导老师 签名指导老师 签名 日期日期 2014 06 09 一一 实验目的和要求实验目的和要求 1 掌握图的主要存储结构 2 学会对几种常见的图的存储结构进行基本操作 二二 实验内容实验内容 1 图的邻接矩阵定义及实现 建立头文件 test13 AdjM h 在该文件中定义图的邻接矩阵存储结构 并 编写图的初始化 建立图 输出图 输出图的每个顶点的度等基本操作实现函 数 同时建立一个验证操作实现的主函数文件 test13 cpp 以下图为例 编 译并调试程序 直到正确运行 2 图的邻接表的定义及实现 建立头文件 test13 AdjL h 在该文件中定义图的邻接表存储结构 并编 写图的初始化 建立图 输出图 输出图的每个顶点的度等基本操作实现函数 同时在主函数文件 test13 cpp 中调用这些函数进行验证 以下图为例 0 1 2 4 6 5 3 0 0 1 1 2 2 3 3 4 3 填写实验报告 实验报告文件取名为 report13 doc 4 上传实验报告文件 report13 doc 到到 BB 注注 下载下载 p256 GraphMatrix cpp 邻接矩阵邻接矩阵 和和 p258 GraphAdjoin cpp 邻接表邻接表 源程序 读懂程序完成空缺部分源程序 读懂程序完成空缺部分 代码 代码 三三 函数的功能说明及函数的功能说明及算法思路算法思路 包括每个函数的功能说明 及一些重要函数的算法实现思路 四四 实验结果与分析实验结果与分析 包括运行结果截图 结果分析等 5 心得体会心得体会 程序比较难写 但是可以通过之前的一些程序来找到一些规律程序比较难写 但是可以通过之前的一些程序来找到一些规律 记录实验感受 上机过程中遇到的困难及解决办法 遗留的问题 意见和 建议等 附录附录 源程序源程序 256 p 255 图的存储结构以 数组邻接矩阵 表示 构造图的算法 include include include include typedef char VertexType 顶点的名称为字符 const int MaxVertexNum 10 图的最大顶点数 const int MaxEdgeNum 100 边数的最大值 typedef int WeightType 权值的类型 const WeightType MaxValue 32767 权值的无穷大表示 typedef VertexType Vexlist MaxVertexNum 顶点信息 定点名称 typedef WeightType AdjMatrix MaxVertexNum MaxVertexNum 邻接矩阵 typedef enum DG DN AG AN GraphKind 有向图 有向网 无向图 无向网 typedef struct Vexlist vexs 顶点数据元素 AdjMatrix arcs 二维数组作邻接矩阵 int vexnum arcnum 图的当前顶点数和弧数 GraphKind kind 图的种类标志 MGraph void CreateGraph MGraph char v w G kind kd 图的种类 printf 输入要构造的图的顶点数和弧数 n scanf d d getchar 过滤回车 printf 依次输入图的顶点名称 ABCD 等等 n for i 0 i G vexnum i scanf c 构造顶点数据 getchar 过滤回车 for i 0 i G vexnum i 邻接矩阵初始化 for j 0 j头顶点名 权值 输入数据 如 A B 23 n else printf 按照 尾顶点名 头顶点名输入数据 A B n for k 0 k c d 输入弧的两个定点及该弧的权重 else scanf c c getchar for i 0 i G vexnum i if G vexs i v break 查找出 v 在 vexs 中的位置 i if i G vexnum cerr vertex ERROR exit 1 for j 0 j G vexnum j if G vexs j w break 查找出 v 在 vexs 中的位置 j if j G vexnum cerr 头顶点名 权值 输入数据 如 A B 23 a b 5 a c 8 c b 7 a d 4 d c 3 输出邻接矩阵 5 8 4 7 3 Press any key to continue void PrintMGraph MGraph switch G kind case DG for i 0 i G vexnum i for j 0 j G vexnum j printf 2 d G arcs i j printf n break case DN for i 0 i G vexnum i for j 0 j G vexnum j if G arcs i j MaxValue printf 2 d G arcs i j else printf printf n break case AG for i 0 i G vexnum i for j 0 j G vexnum j printf 2 d G arcs i j printf n break case AN 完成构造无向网 请模仿编写无向网 for i 0 i G vexnum i for j 0 j G vexnum j if G arcs i j MaxValue printf 2 d G arcs i j else printf printf n break 完成函数 void countdig MGraph G 请完成计算图的入度或初度 if G kind DG G kind DN 计算有向图或网的各个顶点的入度与出度 int outD inD int i j for i 0 i G vexnum i outD inD 0 for j 0 j G vexnum j if G arcs i j 0 for j 0 j G vexnum j if G arcs j i 0 printf c 出度是 d 入度是 d n G vexs i outD inD else 计算无向图或网的度 int i j int Du for i 0 i G vexnum i Du 0 for j 0 j G vexnum j if G arcs i j 0 printf c 的度是 d n G vexs Du 参照 p265 设计深度有限搜索 void DFSMatrix MGraph G int i int n bool visited cout G vexs i visited i true for int j 0 j n j if G arcs i j 0 参照 p268 设计广度有限搜索 void BFSMatrix MGraph G int i int n bool visited const int MaxSize 30 int q MaxSize 0 int front 0 rear 0 cout G vexs i visited i true q rear i while front rear front front 1 MaxSize int k q front for int j 0 j n j if G arcs i j 0 visited j true rear rear 1 MaxSize q rear j void main MGraph G int k printf 请选择图的种类 0 有向图 1 有向网 2 无向图 3 无向网 请选择 scanf d switch k DG DN AG AN case 0 printf 构造有向图 n CreateGraph G DG 采用数组邻接矩阵表示法 构造有向图 break case 1 printf 构造有向网 n CreateGraph G DN 采用数组邻接矩阵表示法 构造有向网 AGG break case 2 printf 构造无向图 n CreateGraph G AG 采用数组邻接矩阵表示法 构造无向图 AGG break case 3 printf 构造无向网 n CreateGraph G AN 采用数组邻接矩阵表示法 构造无向网 AGG break PrintMGraph G 打印图的邻接矩阵 bool visited new bool G vexnum int i cout 按图的邻接矩阵得到的深度优先遍历序列 endl for i 0 i G vexnum i visited i false DFSMatrix G 0 G vexnum visited cout 按图的邻接矩阵得到的广度优先遍历序列 endl for i 0 i G vexnum i visited i false BFSMatrix G 0 G vexnum visited cout 度 头顶点名 输入数据 如 A B a b a c a d c b d c include include include include typedef char VertexType 顶点的名称为字符 const int MaxVertexNum 10 图的最大顶点数 const int MaxEdgeNum 100 边数的最大值 typedef int WeightType 权值的类型 const WeightType MaxValue 32767 权值的无穷大表示 typedef VertexType Vexlist MaxVertexNum 顶点信息 定点名称 邻接矩阵 typedef enum DG DN AG AN GraphKind 有向图 有向网 无向图 无向网 struct EdgeNode 链表边结点 表示弧 int adjvex 存放与头结点顶点有关的另一个顶点在邻接表 数组 中的下标 EdgeNode next 指向链表下一个结点 WeightType info 权重值 或为该弧相关信息 typedef struct VNode 邻接表 表示顶点 VertexType data 顶点数据 顶点名称 EdgeNode firstarc 指向边结点链表第一个结点 VNode AdjList MaxVertexNum typedef struct AdjList vertices int vexnum arcnum 图的当前顶点数和弧数 GraphKind kind 图的种类标志 ALGraph void CreateGraph DG ALGraph int i j k char v w G kind DG 图的种类 printf 输入要构造的有向图的顶点数和弧数 n scanf d d getchar 过滤回车 printf 依次输入图的顶点名称 ABCD 等等 n for i 0 i头顶点名 输入数据 如 A B n for k 0 k c getchar for i 0 i G vexnum i if G vertices i data v break 查找出 v 在 vertices 中的位置 i if i G vexnum cerr vertex ERROR exit 1 for j 0 j G vexnum j if G vertices j data w break 查找出 w 在 vertices 中的位置 i if j G vexnum cerr adjvex j 置入弧尾顶点号 p info MaxValue 图的权值默认为无穷大 p next G vertices i firstarc 插入链表 G vertices i firstarc p void CreateGraph DN ALGraph int i j k char v w WeightType q G kind DN 图的种类 printf 输入要构造的有向网的顶点数和弧数 n scanf d d getchar 过滤回车 printf 依次输入图的顶点名称 ABCD 等等 n for i 0 i头顶点名 权值 输入数据 如 A B 8 n for k 0 k c d getchar for i 0 i G vexnum i if G vertices i data v break 查找出 v 在 vertices 中的位置 i if i G vexnum cerr vertex ERROR exit 1 for j 0 j G vexnum j if G vertices j data w break 查找出 w 在 vertices 中的位置 i if j G vexnum cerr adjvex j 置入弧尾顶点号 p info q 图的权值默认为无穷大 p next G vertices i firstarc 插入链表 G vertices i firstarc p void CreateGraph AG ALGraph int i j k char v w G kind AG 图的种类 printf 输入要构造的有向图的顶点数和弧数 n scanf d d getchar 过滤回车 printf 依次输入图的顶点名称 ABCD 等等 n for i 0 i头顶点名 输入数据 如 A B n for k 0 k c getchar for i 0 i G vexnum i if G vertices i data v break 查找出 v 在 vertices 中的位置 i if i G vexnum cerr vertex ERROR exit 1 for j 0 j G vexnum j if G vertices j data w break 查找出 w 在 vertices 中的位置 i if j G vexnum cerr adjvex j 置入弧尾顶点号 p info MaxValue 图的权值默认为无穷大 p next G vertices i firstarc 插入链表 G vertices i firstarc p 无向图和网的边结点依附于 i j 两个顶点 两方均应添加边 p EdgeNode malloc sizeof EdgeNode 申请弧结点 p adjvex i 置入弧尾顶点号 p info MaxValue 图的权值默认为无穷大 p next G vertices j firstarc 插入链表 G vertices j firstarc p void CreateGraph AN ALGraph int i j k char v w WeightType q G kind AN 图的种类 printf 输入要构造的无向网的顶点数和弧数 n scanf d d getchar 过滤回车 printf 依次输入图的顶点名称 ABCD 等等 n for i 0 i G vexnum i scanf c 构造顶点数据 G vertices i firstarc NULL 初始化指向链表指针 getchar 过滤回车 printf 按照 尾顶点名 头顶点名 权值 输入数据 如 A B 8 n for k 0 k G arcnum k scanf c c d getchar for i 0 i G vexnum i if G vertices i data v break 查找出 v 在 vertices 中的位置 i if i G vexnum cerr vertex ERROR exit 1 for j 0 j G vexnum j if G vertices j data w break 查找出 w 在 vertices 中的位置 i if j G vexnum cerr adjvex j 置入弧尾顶点号 p info q 图的权值默认为无穷大 p next G vertices i firstarc 插入链表 G vertices i firstarc p 无向图和网的边结点依附于 i j 两个顶点 两方均应添加边 p EdgeNode malloc sizeof EdgeNode 申请弧结点 p adjvex i 置入弧尾顶点号 p info q 图的权值默认为无穷大 p next G vertices j firstarc 插入链表 G vertices j firstarc p void dfsAdjoin ALGraph G int i bool visited 深度优先搜索 p266 cout i G vertices i data adjvex if visited j false dfsAdjoin G j visited p p next void bfsAdjoin ALGraph G int i bool visited 广度优先搜索 p268 const int MSize 30 int q MSize 0 int front 0 rear 0 cout G vertices i data adjvex if visited j cout G vertices j data next 完成函数 void countdig ALGraph G 请完成计算图的入度或初度 if G kind DG G kind DN 计算有向图或网的个顶点的入度与初度 int outD inD EdgeNode p k int i j for i 0 inext outD for j 0 jnext if G vertices k adjvex data G vertices i data inD printf c 出度是 d 入度是 d n G vertices i data outD inD else 计算无向图或网的度 int Du EdgeNode p k int i j for i 0 inext Du printf c 度是 d n G vertices i data Du void PrintALGraph ALGraph int i for i 0 i i G vertices i data else printf d c i G vertices i data p G vertices i firstarc 输出依附上面顶点的各条边 while p pr