图——表示与遍历

#图的两种主要表示方法

图有两种常用的表示方法,一种是邻接表法(adjacency-list),另一种是邻接矩阵法(adjacency-matrix)。

邻接表法储存数据更紧凑,适合稀疏的图(sparse graphs)

邻接矩阵法适合密集的图(dense graphs)

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

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

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

邻接矩阵法使用一个 $|V| \times |V|$ 的矩阵表示图,如果两个顶点间有边,那么相对应的 $G[u][v]$ 值为 1(或者权重) ,否则为 0 。观察无向图的邻接矩阵,矩阵以主对角线为轴对称,因此我们几乎可以将无向图的邻接矩阵空间占用减半。无论有向图还是无向图,邻接矩阵法的空间复杂度都是 $\Theta(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 的时间复杂度是 $\mathcal{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 的时间复杂度是 $\Theta(V + E)$


#相关内容

图——拓扑排序

图——连通性