考研系列-数据结构第六章：图（下）
目录
写在前面
一、图的遍历
1.广度优先遍历（BFS）
(1)联系树的广度优先遍历
(2)算法实现
①无向图的广度优先遍历
②有向图的广度优先遍历
(3)复杂度分析
(4)广度优先生成树、森林
(5)总结
2.深度优先遍历（DFS）
(1)联系树的深度优先遍历
(2)算法实现
(3)复杂度分析
(4)深度优先生成树
(5)图的遍历和图的连通性
3.知识点总结
4.习题总结
(1)选择题
(2)简答题
二、图的应用
1.最小生成树
(1)什么是最小生成树
(2)Prim算法
(3)Kruskal算法
(4)二者对比及总结
2.最短路径问题
(1)广度优先遍历（BFS）-针对无权图
(2)Floyd算法（弗洛伊德算法）
①算法思想
②算法实例
③Floyd算法可以用于负权图
(3)Dijkstra算法（迪杰斯特拉算法）
①BFS算法存在的局限性
②Dijkstra算法详解
③对比Prim算法
④Dijkstra算法不适用于负权图
(4)三种算法对比总结
3.有向无环图（DAG）
(2)有向无环图描述表达式
(3)练习
4.AOV网
(1)什么是AOV网络？
(2)拓扑排序
①算法思想
②代码实现（图示实现过程）
③时间复杂度分析
(3)逆拓扑排序
(4)总结
5.AOE网
(1)什么是AOE网
(2)求关键路径
(3)关键活动、关键路径的特性
(4)总结
6.易错题总结
(1)本节重要知识点
(2)选择题
(3)简答题
三、本章总结
四、参考
写在前面
关于图的一些代码实现可以参考下面文章整理内容：
图相关代码-CSDN博客文章浏览阅读97次。【代码】图相关代码。https://blog.csdn.net/hehe_soft_engineer/article/details/134235925
一、图的遍历
1.广度优先遍历（BFS）
包括深度优先遍历和广度优先遍历
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!
