数据结构实验一图剖析

北京邮电大学信息与通信工程学院 第 1 页 数据结构实验报告 实验名称 实验二 图 学生姓名 佘晨阳 班 级 2014211117 班内序号 20 学 号 2014210491 日 期 2015 年 12 月 05 日 1 实验要求 根据图的抽象数据类型的定义 使用邻接矩阵或邻接表实现一个图 图的基本功能 1 图的建立 2 图的销毁 3 深度优先遍历图 4 广度优先遍历图 5 使用普里姆算法生成最小生成树 6 使用克鲁斯卡尔算法生成最小生成树 7 求指定顶点到其他各顶点的最短路径 8 其他 比如连通性判断等自定义操作 编写测试 main 函数测试图的正确性 2 程序分析 本实验要求掌握图基本操作的实现方法 了解最小生成树的思想和相关概念 了 解最短路径的思想和相关概念 学习使用图解决实际问题的能力 2 1 存储结构 存储结构 1 不带权值的无向图邻接矩阵 2 带权值的无向图邻接矩阵 3 带权值的有向图邻接矩阵 1 不带权值的无向图邻接矩阵 北京邮电大学信息与通信工程学院 第 2 页 2 带权值的无向图邻接矩阵 3 带权值的有向图邻接矩阵 备注备注 1 在使用打印元素 在使用打印元素 BFS DFS 采用无权值的无向图邻接矩阵存储方式采用无权值的无向图邻接矩阵存储方式 2 在使用在使用 PRIM KRUSKAL 3 在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式 2 2 关键算法分析 北京邮电大学信息与通信工程学院 第 3 页 一 图的邻接矩阵构造函数一 图的邻接矩阵构造函数 1 关键算法 template Graph Graph f a int n int e 带权值的图的构造函数 int i j k height f s1 s2 vnum n arcnum e for k 0 k n k vertex k a k 初始化顶点 for k 0 k n k for i 0 i n i arc k i 1 if i k arc k i 0 初始化权值的大小 visited k 0 cout endl for k 0 k e k 初始化边 cout s1 s2 height arc convert s1 convert s2 height arc convert s2 convert s1 arc convert s1 convert s2 采用无向图带权值的 邻接矩阵 cout endl cout 所得邻接矩阵为 endl for k 0 k n k for i 0 i n i if arc k i 1 cout else cout arc k i 打印邻接矩阵的格式 cout endl cout endl 2 算法的时间复杂度 北京邮电大学信息与通信工程学院 第 4 页 有构造可知 初始化时其时间复杂度 O n2 二 深度优先便利二 深度优先便利 DFS 1 关键算法 从某顶点 v 出发并访问 访问 v 的第一个未访问的邻接点 w 访问 w 的第一个未访问的邻接点 u 若当前顶点的所有邻接点都被访问过 则回溯 从上一级顶点的下一个未访问过的顶点 开始深度优先遍历 直到所有和 v 路径相通的顶点都被访问到 2 代码图解 深度优先遍历示意图 3 代码详解 template void Graph DFS int v cout vertex v visited v 1 for int j 0 j 1 DFS j 当存在回路时 则连通深一层遍 历 4 时间复杂度 时间复杂度 O n2 空间复杂度 栈的深度栈的深度 O n 辅助空间辅助空间 O n 北京邮电大学信息与通信工程学院 第 5 页 三 广度遍历三 广度遍历 BFS 1 关键算法 访问顶点 v 依次访问 v 的所有未被访问的邻接点 v1 v2 v3 分别从 v1 v2 v3 出发依次访问它们未被访问的邻接点 反复 直到所有和 v 路径相通的顶点都被访问到 2 代码图解 3 代码详解 1 初始化队列 Q 2 访问顶点 v visited v 1 3 while 队列非空 3 1 v 队头元素出队 3 2 访问队头元素的所有未访问的邻接点 4 时间复杂度 时间复杂度 O n2 空间复杂度 辅助空间辅助空间 O n 四四 最小生成树最小生成树 普里姆算法普里姆算法 1 关键思路 一般情况下 假设 n 个顶点分成两个集合 U 包含已落在生成树上的结点 和 V U 尚未落 在生成树上的顶点 则在所有连通 U 中顶点和 V U 中顶点的边中选取权值最小的边 主数据结构 邻接矩阵 辅助数据结构 北京邮电大学信息与通信工程学院 第 6 页 int adjvex MAXSIZE U 集中的顶点序号 int lowcost MAXSIZE U V U 的最小权值边 2 代码图解 北京邮电大学信息与通信工程学院 第 7 页 北京邮电大学信息与通信工程学院 第 8 页 3 代码详解 template void Graph Prim for int i 0 i vnum i 辅助数组存储所 有到的 V0 边 adjvex i 0 lowcost i arc 0 i lowcost 0 0 for int j 1 j vnum j 循环 n 1 次 int k Mininum lowcost 求下一个顶 点 cout vertex adjvex k vertex k endl lowcost k 0 U U Vk for int j 0 j vnum j 设置辅助数组 if lowcost j 0 adjvex j k 北京邮电大学信息与通信工程学院 第 9 页 4 时间复杂度 时间复杂度 O n2 适合稠密图 五五 最小生成树最小生成树 克鲁斯卡尔算法克鲁斯卡尔算法 1 关键思路 先构造一个只含 n 个顶点的子图 SG 然后从权值最小的边开始 若它的添加不使 SG 中产 生回路 则在 SG 上加上这条边 如此重复 直至加上 n 1 条边为止 2 代码图解 3 代码详解 template void Graph Kruskal 最小生成树 kruskal 算法 cout Krusal 算法结果为 endl int vset MAXSIZE for int i 0 i vnum i vset i i int k 0 j 0 while k vnum 1 int m vedgelist j fromv n vedgelist j endv int sn1 vset m int sn2 vset n 两个顶点分属 北京邮电大学信息与通信工程学院 第 10 页 不同的集合 if sn1 sn2 cout vertex m vertex n endl k for int i 0 i vnum i if vset i sn2 vset i sn1 集合 sn2 全 部改成 sn1 j 4 时间复杂度 时间复杂度 O nlogn 适合稀疏图 六 最短路径六 最短路径 Dijkstra 算法算法 1 关键代码 按路径长度递增的次序产生源点到其余各顶点的最短路径 1 设置集合 s 存储已求得的最短路径的顶点 2 初始状态 s 源点 v 3 叠代算法 直接与 v 相连的最近顶点 vi 加入 s 从 v 经过 vi 可以到达的顶点中最短的 加入 s 2 代码图解 北京邮电大学信息与通信工程学院 第 11 页 3 代码详解 emplate void Graph ShotPath f x 关于最短路 径的初始化 int v convert x for int i 0 i vnum i 初始化路径和 点 s i 0 disk i arc v i if disk i maxs path i v else path i 1 s v 1 disk v 0 path v 1 for int i 0 i vnum i 反复经过从该 点到其他点的路径 if v FindMin 1 continue s v 1 for int j 0 j arc v j disk v 北京邮电大学信息与通信工程学院 第 12 页 disk j arc v j disk v path j v Print 打印路径 长度和遍历 4 时间复杂度 时间复杂度为 n 2 七 判断连通图算法七 判断连通图算法 template bool Graph judgegraph DFS convert vertex 0 if count vnum cout 该图为连通图 输入成功 endl return false else cout 该图不为连通图 请重新输入 endl return true 时间复杂度 n 2 3 程序运行结果 1 测试主函数流程 北京邮电大学信息与通信工程学院 第 13 页 函数流程图 1 输入图的连接边并打印 构造下面所示图的邻接矩阵 北京邮电大学信息与通信工程学院 第 14 页 2 判断图连通是否成功判断图连通是否成功 3 BFS DFS PRIM 算法的实现 北京邮电大学信息与通信工程学院 第 15 页 4 克鲁斯卡尔算法实现过程 4 有向图邻接矩阵的构建 北京邮电大学信息与通信工程学院 第 16 页 插入 V0 位置后打印距离并开始回溯 总结 1 调试时出现的问题及解决的方法 问题一 prim 算法中 解决方法 调整循环条件 修正函数体注意有无 Next 的区别 北京邮电大学信息与通信工程学院 第 17 页 问题二 BFS 和 DFS 同时在一个类里作用时会输出错误 解决方案 每次 BFS DFS 使用时都把 visited 数组初始化一遍 问题三 在最短路径 经常出现了停止输入的情况 解决方法 改 return 为 continue 并修改打印算法 2 心得体会心得体会 通过本次实验 基本熟练掌握了 c 基本语句 尤其对图的结构及应用有了较深了 解 调试代码时尽量做到完成一个代码段调试一次 可以最快检测出错误所在 类的封装 和调用 类的共有成员和私有成员的设置 3 下一步的改进下一步的改进 第一 设置增加图节点和边的函数 第二 实现图形化输出图的路径的功能 第三 主函数设计简单 不要过