图（Graph）

为什么要使用图？

如果你有一个编程问题可以通过顶点和边表示出来，那么你就可以将你的问题用图画出来，然后使用著名的图算法（比如广度优先搜索 或者 深度优先搜索）来找到解决方案。

基本知识点

• 阶（Order）、度：出度（Out-Degree）、入度（In-Degree）
• 树（Tree）、森林（Forest）、环（Loop）
• 有向图（Directed Graph）、无向图（Undirected Graph）、完全有向图、完全无向图
• 连通图（Connected Graph）、连通分量（Connected Component）
• 存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）

与图相关的算法

• 图的遍历：深度优先、广度优先
• 环的检测：有向图、无向图
• 拓扑排序
• 最短路径算法：Dijkstra、Bellman-Ford、Floyd Warshall
• 连通性相关算法：Kosaraju、Tarjan、求解孤岛的数量、判断是否为树
• 图的着色、旅行商问题等

必会知识点

• 图的存储方式：邻接矩阵、邻接列表

两种储存方式如何抉择？

假设 V 表示图中顶点的个数，E 表示边的个数。

所以，当图比较密集，顶点较少时，每一个顶点都和大多数其他顶点相连，那么相邻矩阵更合适。反之，在 稀疏图的情况下，每一个顶点都只会和少数几个顶点相连，这种情况下相邻列表是最佳选择。

• 图的遍历（广度优先，深度优先）

二部图的检测、树的检测、华北的检测：有向图、无向图

拓扑排序

联合——查找算法

最短路径