连通图一笔画.doc

沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称 数据结构课程设计数据结构课程设计 课程设计题目 连通图一笔画的判定与求解连通图一笔画的判定与求解 院 系 计算机学院 专 业 计算机科学与技术 班 级 84010102 学 号 2008040101042 姓 名 刘冬 指导教师 范纯龙 沈阳航空航天大学课程设计报告 目目 录录 1 算法分析算法分析 1 1 1 假设条件 1 1 2 算法描述 1 1 2 1 无向图的存储结构和连通图的判定 1 1 2 2 欧拉回路和欧拉通路的求解 1 2 系统设计系统设计 3 2 1 设计说明 3 2 2 数据结构描述 3 2 3 MAIN 主函数 4 2 4 INPUT ARCS 邻接矩阵建立函数 5 2 5 BFSTEST 连通图判定函数 6 2 6 EULER 欧拉回路和欧拉通路求解函数 7 3 系统实现系统实现 8 3 1 错误分析 8 3 2 实现结论 9 参考文献参考文献 10 附附 录 关键部分程序清单 录 关键部分程序清单 11 沈阳航空航天大学课程设计报告 0 1 算法分析 1 1 假设条件假设条件 连通图采用邻接矩阵存储 最大为 200 200 的邻接矩阵 并且输入的的是顶 点的位置 整数 输入的数据为无向图的顶点数和边数 顶点数为大于 0 小于 200 的整数 边 数为非负小于 200 的整数 还有邻接矩阵的值 起点和终点 都为非负整数 输入的无向图 可为连通也可不连通 也可输入单个顶点的图 程序会进行 判断 1 2 算法描述算法描述 1 2 1 无向图的存储结构无向图的存储结构和连通图的判定和连通图的判定 采用邻接矩阵存储无向图 利用二维数组 Graph 200 200 表示邻接矩阵 输入结点数 v 和边数 e 还有邻接矩阵的值 起点和终点 如果结点之间有边 则数组中相应位置的数赋值 1 对于无向图任意两个顶点都是连通的 即都能够互相到达 则此无向图是连 通图 连通图的判断 如果是连通图则返回 1 不是返回 0 创建队列 将第一 个顶点入队 a i i 为顶点的位置 用来标记结点是否能到达 能到达则赋值 1 不能则赋值 0 a 0 赋初值为 1 a 1 a v 1 赋初值 0 队首元素出队 判 断其能到达的顶点 判断关联关系 如果能到达 则相应的 a i 赋值 1 并将该 顶点入队 然后反复这样的判断寻找过程 直到队列为空为止 如果此时还有顶 点没被到达 即 a 1 a v 1 中仍有为 0 的 则返回值 0 如果全部顶点都能到 达 则返回值 1 1 2 2 欧拉回路和欧拉通路的求解欧拉回路和欧拉通路的求解 根据欧拉定理 如果欧拉图 v 个顶点的度都为偶数则存在欧拉回路 此路径 是起点为任意顶点 终点为起点的回路 而如果 v 个顶点中只有两个顶点的度为 沈阳航空航天大学课程设计报告 1 奇数 其余的都为偶数 则存在欧拉通路 此路径的起点为奇数度顶点之一 终 点为另一个奇数度顶点 因此 连通图一笔画的判定与求解就是对输入的无向连通图是否存在欧拉回 路和欧拉通路的判定和求解 当连通图中所有顶点的度都为偶数时 连通图就存 在欧拉回路 且起点为任意顶点 终点也为该顶点 当连通图中只有两个顶点的 度为奇数时 连通图就存在欧拉通路 起点为这两个奇数度顶点之一 终点为另 一个奇数度顶点 利用深度优先遍历和栈的基本操作来实现的欧拉算法求解欧拉回路和欧拉通 路 算法就是深度优先遍历连通图 k 来标记当前访问的节点是否还有邻接边可 供访问 初值 0 将本次遍历边所经由的点入栈 寻找第一条与其关联的边和顶 点 k 赋值 1 边已访问 删除此边 递归调用此函数寻找与该关联的顶点相 关联的边和顶点 直到相关联的边都被访问完为止 如果上一个顶点还有没被访 问的边 则将栈顶元素出栈 并恢复上一层被删除的边 从上一个顶点的下一条 未被访问得边继续深度优先遍历此图 如果遍历完所有的边 即栈的长度等于边 数 e 则将最后的顶点入栈 最后输出栈内元素即为所求 欧拉回路和欧拉通路 的求解算法区别在于 欧拉回路的遍历起点任意 而欧拉通路的遍历起点必须是 度为奇数的的两个顶点之一 沈阳航空航天大学课程设计报告 2 2 系统设计 2 1 设计说明设计说明 该程序设计共包括四大模块 主函数模块 邻接矩阵建立模块 连通图判定 模块 欧拉回路和欧拉通路求解模块 主函数中调用了其他所有三个模块 连通 图的判定模块与欧拉回路和欧拉通路的求解模块都调用了邻接矩阵建立模块中建 立的邻接矩阵 函数模块关系如图 2 1 1 所示 图 2 1 1 函数模块关系图 2 2 数据结构描述数据结构描述 该程序主要用到了栈 队列 图等数据结构 它们的表示和实现如下所示 栈的顺序存储表示 定义了初始分配量 STACK INIT SIZE 分配增量 STACKINCRMENT 栈底和栈顶指针 base top 还有当前栈的长度 stacksize define STACK INIT SIZE 100 define STACKINCRMENT 10 typedef struct int base int top int stacksize SqStack 连通图一笔画的判定与求解 主函数模 块 邻接矩阵建 立模块 连通图判定 模块 欧拉回路 和欧拉通 路求解模 块 沈阳航空航天大学课程设计报告 3 队列的链式存储表示 定义了队列的结点结构体还有队列的队首和队尾指针 结点结构体中定义了数据域 data 为整型和指向下一个结点的指针 队首队尾指针 都是指向队列结点的指针 typedef struct QNode int data struct QNode next QNode QueuePtr typedef struct QueuePtr front QueuePtr rear LinkQueue 2 3 main 主函数 主函数 功能 连接各个函数 确定他们的执行顺序和条件 简单的工作过程 主函数调用邻接矩阵建立函数建立无向图的邻接矩阵 然 后调用连通图判定函数判断该无向图是否是连通图 是则判断是否存在欧拉回路 或通路 存在 则调用欧拉回路或欧拉通路求解函数求出欧拉回路或欧拉通路 图 2 3 1 main 主函数 开始 是连通图 Y 顶点度都为偶数 欧拉回路求解 N 度为奇数的的顶点 只有两个 Y 欧拉通路求解 N 打印 不含 欧拉回路和 欧拉通路 N 打印 该图不 是连通图 建立无向图的邻接矩阵 Y 结束 沈阳航空航天大学课程设计报告 4 2 4 Input Arcs 邻接矩阵建立函数 邻接矩阵建立函数 功能 根据输入的顶点数和边数还有邻接矩阵的值建立无向图的邻接矩阵 参数含义 Graph G z h 1 结束 沈阳航空航天大学课程设计报告 5 2 5 BFSTest 连通图判定函数连通图判定函数 功能 判断输入的无向图是否为连通图 参数含义 Graph G 为之前建立好的无向图的邻接矩阵 简单的工作过程 先创建一个队列 队列不为空 则将队首元素出队 并用 x 返回 寻找与 x 相关联的顶点 i 并将被访问过的顶点入队 然后继续前面的 过程 直到队列为空为止 如果所有顶点都被访问完 则此图是连通图 图 2 5 1 BFSTest 连通图判定函数 开始 创建队列 队列不为空 队首元素出队 用 x 返 回 寻找与 x 相关联的顶点 i a i 1 则将 i 入队 有未到顶点 不是连通图 返回 1 是连通图 返回 0 结束 Y Y N N 沈阳航空航天大学课程设计报告 6 2 6 Euler 欧拉回路和欧拉通路求解函数 欧拉回路和欧拉通路求解函数 功能 求解连通图的欧拉回路或欧拉通路并输出 参数含义 Graph Push S x for i t i0 k 1 G i x 0 G x i 0 DFS G S i 0 break if k 0 Pop S n GetTop S m G x m 1 G m x 1 a x 1 if StackLength S e Pop S n DFS G S m a else Push S x int BFSTest Graph G int a 200 x i k 0 LinkQueue Q InitQueue Q EnQueue Q 0 for i 0 i v i a i 0 a 0 1 while QueueEmpty Q 沈阳航空航天大学课程设计报告 11 DeQueue Q x for i 0 i0 if a i 1 a i 1 EnQueue Q i for i 0 iV d m 1 Pop S n void Input Arce Graph printf 请输入顶点数和边数 n scanf d d 沈阳航空航天大学课程设计报告 12 if v 1 else if v 0i v i for int j 0 j v j G i j 0 printf 请输入邻接矩阵的值 起点 数字 终点 数字 n for int k 0 k0 G z 1 h 1 1 else printf 输入数据不合法 else printf 输入数据不合法 课程设计总结 课程设计总结 本次数据结构课程设计使我对这半学期所学的数据结构的相关知识有了更 深的理解和掌握 并初步具备了运用所学知识设计相应的数据结构来解决问题 的能力 虽还不是很熟练 但我会继续努力 不断学习和实践 提升运用所学 解决问题的能力 在编程过程中 我更加熟练地运用了开发环境 像单步跟踪 做标记 进入函数等等调试方法也运用的比以前更加熟练 而且还帮助我解决 了不少程序运行中的逻辑性问题 对我的编程能力提高起到了很大的促进作用 本次课设代码全是我自己独立完成的 这对我的专业能力既是一次检验也是一 次提高 在