1. 图基本介绍
前面我们学了线性表和树，线性表局限于一个直接前驱和一个直接后继的关系，树也只能由一个直接前驱也就是父节点。当我们需要表示多对多的关系时，我们就用到了图。
1.1 图的常用概念
在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对(连接)。顶点圆圈表示，边就是这些圆圈之间的连接。顶点之间通过边连接。
顶点有时也称为节点或者交点，边有时也称为链接。
一个图可以表示一个社交网络，每一个人就是一个顶点，互相认识的人之间通过边联系。
图有各种形状和大小。边可以有权重(weight)，即每一条边会被分配一个正数或者负数值。考虑一个代表航线的图。各个城市就是顶点，航线就是边。那边边的权重可以是飞行时间，或者机票价格。
边可以是有方向的。在上面提到的例子中，边是没有方向的。例如，如果 A 认识 B，那么 B 也就认识 A。相反，有方向的边意味着是单方面的关系。一条从顶点 X 到 顶点 Y 的边是将 X 联向 Y，不是将 Y 联向 X。
1.2 为什么使用图
如果你有一个编程问题可以通过顶点和边表示出来，那么你就可以将你的问题用图画出来，然后使用著名的图算法(比如广度优先搜索或者深度优先搜索)来找到解决方案。
例如，假设你有一系列任务需要完成，但是有的任务必须等待其他任务完成后才可以开始。你可以通过非循环有向图来建立模型：
每一个顶点代表一个任务。两个任务之间的边表示目的任务必须等到源任务完成后才可以开始。比如，在任务B 和任务D都完成之前，任务C不可以开始。在任务A完成之前，任务B和D都不能开始。
现在这个问题就通过图描述清楚了，你可以使用深度优先搜索算法来执行拓扑排序。这样就可以将所有的任务排入最优的执行顺序，保证等待任务完成的时间最小化。(这里可能的顺序之一是：A，B，D，E，C，F，G，H，I，J，K)
2. 图的表示方式
图就是一堆顶点和边对象而已，但是怎么在代码中来描述呢？
图的表示方式有两种：二维数组表示(邻接矩阵)；链表表示(邻接列表)
2.1 邻接矩阵
在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连，如果相连这个值表示的是相连边的权重。例如，如果顶点A到顶点B有一条权重为 5.6 的边，那么矩阵中第A行第B列的位置的元素值应该是 5.6：
往这个图中添加顶点的成本非常昂贵，因为新的矩阵结果必须重新按照新的行/列创建，然后将已有的数据复制到新的矩阵中。
2.2 邻接列表
邻接列表：在邻接列表实现中，每一个顶点会存储一个从它这里开始的边的列表。比如，如果顶点A有一条边到B，C和D，那么A的列表中会有 3 条边：
邻接列表只描述了指向外部的边。A有一条边到B，但是B没有边到A，所有A没有出现在B的邻接列表中。查找两个顶点之间的边或者权重会比较费时，因为遍历邻接列表直到找到为止。
所以使用哪一个呢？大多数时候，选择邻接列表是正确的。
3. 图的深度优先介绍
3.1 图遍历介绍
一般图有那么多个节点，如何遍历这些节点，需要特定策略。 一般有两种访问策略：深度优先遍历，广度优先遍历
3.2 深度优先遍历基本思想
深度优先遍历，从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先遍历的策略就是首先访问，第一个邻接节点，然后再以这个被访问的邻接节点作为初始节点，访问它的第一个邻接节点，可以这样理解每次都在访问完当前节点后首先访问当前节点的第一个邻接节点。
3.3 深度优先算遍历算法步骤
- 访问初始顶点 x，访问后需要标记 x 已经访问过，不能再次重读访问
- 查找顶点 x 的第一个邻接点 y
- 如果y存在，则继续执行下面步骤，如果y不存在，则回到第 1 步，将从x的下一个顶点继续
- 如果 y 未被访问过，对y进行深度优先遍历，则是把y当做另一个x，然后执行 123 步
- 查找顶点x的y临界点的下一个邻接点，转到步骤3
4. 图的广度优先介绍
4.1 广度优先遍历基本思想
类似于一个分层搜索的过程，广度优先遍历(Breadth-First-Search)需要使用一个队列以保持访问过的节点的顺序，以便按这个顺序来访问这些节点的邻接节点。
4.2 广度优先遍历算法分析
- 访问初始节点 v 并标记节点 v 已访问
- 节点 v 加入队列
- 当队列非空时，继续执行，否则算法结束
- 出队列，获取队头节点 u
- 查找节点 u 的第一个邻接节点 w
- 若节点 u 的邻接节点 w 不存在，则转到步骤3；否则循环执行以下三个步骤： 6.1 若节点 w 尚未被访问，则访问节点 w 并标记记为已访问 6.2 节点 w 入队列 6.3 查找节点 u 的继 w 邻接节点后的下一个邻接节点 w，转到步骤 6