【读书笔记】数据结构与算法之美 第9章 图
《数据结构与算法之美》，王争 著
标签：数据结构、算法
第9章 图
一、图的表示
这一部分介绍了
图的定义
邻接矩阵的存储方法
邻接表的存储方法
如何用图存储微博、微信等社交网络中的好友关系
笔记：邻接表（邻接表+逆邻接表）存储结构适合存储大规模的满足网状结构特征的数据集；将邻接表中的链表改为其他支持快速查找的数据结构，如平衡二叉树、跳表和哈希表等，即优化了存储空间，又保证了查询效率高。
二、深度优先搜索和广度优先搜索
这一部分介绍了
什么是搜索算法
广度优先搜索
深度优先搜索
如何用广度优先搜索找出社交网络中的三度好友关系
笔记：深度优先搜索和广度优先搜索是数据结构和算法课程和教材中，图部分的必学知识点，原因无他，就是太常用，太基本的图搜索算法。
三、拓扑排序
这一部分介绍了
什么是拓扑排序
利用Kahn算法实现拓扑排序
利用深度优先搜索实现拓扑排序
利用拓扑排序检测环
如何利用拓扑排序确定代码源文件的编译依赖关系
笔记：图的拓扑排序也是一种常用和基本的图算法，教材中的两种实现算法也是算法设计的经典案例。
四、单源最短路径
这一部分介绍了
最短路径算法介绍
Dijkstra算法的原理与实现
Dijkstra算法的性能分析
Dijkstra算法思想的应用（作者介绍了一个翻译系统的实现）
单源最短路径的应用：地图软件如何计算最优出行路线
五、多源最短路径
这一部分介绍了
Floyd的原理与实现
Floyd算法的性能分析
如何用Floyd算法解决传递闭包问题
六、启发式搜索
这一部分介绍了
什么是次优路线
A*算法的原理与实现
A*算法与Dijkstra算法的对比
如何用A*算法实现游戏中的寻路功能
笔记：图的路径搜索问题是经典问题，教材中必讲，考试必考，科研和实际工程项目中应用广泛。教材中的内容都是基本的原理，掌握这些原理，为科研和实际工程项目中的实际应用打下良好的基础。
七、最小生成树
这一部分介绍了
什么是最小生成树
Kruskal算法的原理与实现
Prim算法的原理与实现
如何随机生成游戏中的迷宫地图
八、最大流
这一部分介绍了
什么是最大流
Ford-Fulkerson方法
Edmonds-Karp算法
最大流的一个非常经典应用：最大二分匹配
如何解决单身交友联谊中的最多匹配问题
本章笔记：图及其相关算法是数据结构和算法教材中必有，必考部分，图是一种比较复杂（或称为高级）的数据结构，图的相关算法也比较复杂，但是图的经典算法，应用广泛，不得不学；而且经典图算法的算法设计思路或方法也是算法设计方法的经典案例。
