图——表示与遍历

图的两种主要表示方法

图有两种常用的表示方法，一种是邻接表法（adjacency-list），另一种是邻接矩阵法（adjacency-matrix）。

邻接表法储存数据更紧凑，适合稀疏的图（sparse graphs）

邻接矩阵法适合密集的图（dense graphs）

下图来自 CLRS，很好的展示两种不同的表示方法。

 

在邻接法表示中，一个图 G=(V,E) 由含有 |V| 个链表头的数组 Adj 构成。每个链表包括相对应的顶点能直接到达的所有顶点。无向图的邻接表所有链表的长度和为 2|E|，即边的个数的 2 倍，有向图的邻接表的所有链表长度和为 |E|。无论有向图还是无向图，邻接表法的空间复杂度都为 Θ(V+E)。

邻接表的缺点是，它无法快速给出两个顶点间是否有直接相连的边。

邻接矩阵法使用一个 |V|×|V| 的矩阵表示图，如果两个顶点间有边，那么相对应的 G[u][v] 值为 1（或者权重） ，否则为 0 。观察无向图的邻接矩阵，矩阵以主对角线为轴对称，因此我们几乎可以将无向图的邻接矩阵空间占用减半。无论有向图还是无向图，邻接矩阵法的空间复杂度都是 Θ(V^2) ，与边的个数无关

邻接表与邻接矩阵两种方法，可以清晰的体现，时间换空间，空间换时间，这种“计算守恒定律”（这句话是我自己编的）。

广度优先搜索 （又称宽度优先搜索，Breadth-First Fearch, BFS）

给定图 G = (V, E), 以及一个顶点 s，BFS会搜索所有可达的顶点，计算从初始 s 到目标顶点 t 的距离（距离指经过的边的数量）。BFS 还会生成一个广度优先树，以 s 为根，包括所有的可达顶点。对于图中的两个顶点 s 以及 t ，最短的路径就是以 s 为根的广度优先树中，根 s 到 t 的路径。

BFS 之所以叫 BFS，就是因为它“均匀” 的发现所有顶点，在距离初始顶点 s k + 1 距离的顶点被发现前，所有距离为 k 的顶点都已经被发现。BFS 在发现顶点时，使用颜色来标记，初始时所有的顶点都为白色，当一个顶点被发现时，它被标记为灰色（或者黑色），如果一个顶点是黑色，那么它周围直接连接的所有顶点，只能灰色或者黑色，而灰色顶点周围可以有白色顶点。

BFS 构建一个广度优先树，初始顶点为根。扫描已发现顶点 u 的邻接表，每当发现（第一次遇见）一个白色顶点 v 的时候，将顶点 v 以及边 (u, v) 加入到树，称顶点 u 为顶点 v 的在树中的前序顶点(predecessor)或者父顶点(parent)。因为一个顶点只能被发现一次，一个顶点最多有一个父顶点。在广度搜索树中，祖先顶点与孙子顶点是相对初始顶点 s 来说的。

BFS使用队列（Queue)实现，以下的代码来自 CLRS，图用邻接表来表示时，BFS 的时间复杂度是 O(V+E)。

 下面是 BFS 的例子，同样来自 CLRS。

BFS 可以查找两顶点间的最短距离。

深度优先搜索 （Depth-First Search, DFS）

深度优先搜索首先向更深处搜索，首先搜索最近发现的，还有未发现的边的顶点。一旦某个顶点的所有边都搜索完毕，就回溯，直到所有的可达的顶点都被搜索到。如果依旧有未发现的顶点，DFS 选取一个未搜索顶点作为新的初始顶点，继续搜索，直到所有的顶点都被搜索。

对比广度优先与深度优先，你可能会发现（认为），BFS 只能搜索某个初始顶点的所有可达顶点而 DFS 搜素所有顶点。其实并不是这样，BFS 也可以选取其他初始顶点继续搜索，但是我们一般不这样做。BFS 通常用来寻找最短路径，而 DFS 通常作为遍历图的一种方法。两者应用场景不同。

因为 DFS 默认搜索所有的顶点，最后我们可能会得到一片深度搜索树森林。与广度优先一样，未发现的顶点为白色，正在探索的顶点为灰色，完全探索的顶点为黑色。深度优先搜索对每个被搜索的顶点 v，会记录两个时间，一个是搜索这个顶点的开始时间 v.d，另一个是搜索完毕当前顶点的时间 v.f，当 t<v.d 时，顶点为白色，当 v.d<t<v.f 时，顶点为灰色，当 v.f<t 时，顶点为黑色。

下面是 CLRS 中 DFS 的伪代码。

CLRS 中 DFS 过程例子。

 图用邻接表来表示时，DFS 的时间复杂度是 Θ(V+E)。