22. 基本的图算法

本章介绍图的表示和搜索。
许多的图算法在一开始都会先通过搜索来获得图的结构，其他一些图算法则是对基本的搜索加以优化。
可以说，图的搜索技巧是整个图算法领域的核心。

图的表示

$G = (V, E)$

图G由结点的集合V 和 边的集合E 组成

可以用两种方法表示，一种是邻接链表（下图b），一种是邻接矩阵（下图c）。
邻接链表一般用于表示稀疏图（边数$|E|$远小于$|V|^2$），默认都使用邻接链表表示。在稠密图（$|E|$接近$|V|^2$）的情况下，倾向使用邻接矩阵。

无向图：

有向图：

邻接链表表示

由一个链表数组$Adj$组成，数组大小为$|V|$，链表$Adj[u]$存储了结点$u$出发的边的终点。
比如上面无向图中，从结点1出发有两条边，边的终点分别是2和4，反应到邻接链表中就是$Adj[1]$存储了两个节点2和4。

邻接链表需要的存储空间为$\Theta(|V|+|E|)$

邻接矩阵表示

由一个$|V| \times |V|$ 的矩阵$A = (a_{ij})$表示，并满足以下条件：

$a_{ij} = \left \{ \begin{aligned} & 1 & if (i, j) \in E, &\\ & 0 & other, & \end{aligned} \right.$

当边有权重时，$a_{ij}$可以存储权重值。

邻接矩阵需要的存储空间为$\Theta(|V|^2)$

一些术语

一个结点的出度为，从这个结点触发的边的个数。
一个结点的入度为，到达这个结点的边的个数。

广度优先搜索

思路：利用一个队列，首先将头结点插入队列，循环的取出队列中的一个结点，并将于该结点相连的结点加入队列，直到队列变空，搜索结束。

辅助的给每个结点加入三个属性：

• color：白色表示还未被搜索，灰色表示加入队列，黑色表示从队列里出来
• d：该节点在第几轮被发现
• $\boldsymbol{\pi}$：该结点的前驱（结点第一次被发现时，正在查询的结点）

下面是广度优先搜索的伪代码和事例：

广度优先搜索的正确性

TODO

广度优先搜索的性质

最短路径

从某个结点u做广度优先搜索，可以找出这个结点到其他结点的最短路径。

结点v和结点u的最短路径距离为v.d

从结点v开始 循环列举前驱结点，就是结点v和结点u的最短路径中经过的结点。

广度优先树

广度优先搜算中，我们在$\pi$属性中存储了每个结点的前驱结点，另前驱结点作为该结点的父节点，我们可以得到一个广度优先树。发现新结点的边为树边。

深度优先搜索

思路：尽可能的深入。总是对最近发现的结点v出发的边进行探索，直到结点v出发的边全部被发现时，回溯到v的前驱结点继续探索，直到从源节点出发所有可以到达的结点都被发现。这时如果还有未被搜索的结点，则再随机找一个未被搜索的结点作为源节点进行搜索。

因为可能从一个源节点出发不能搜索到所有结点，所以深度优先搜索会产生多个深度优先树组成深度优先深林。

辅助的给每个结点加入四个属性：

• color：白色表示还未被搜索，灰色表示已被发现但出发的边还没搜索完，黑色表示已被发现并且出发的边已被搜索完
• d：该节点的发现时间
• f：该结点出发搜索结束的时间
• $\boldsymbol{\pi}$：该结点的前驱（结点第一次被发现时，正在查询的结点）

下面是深度优先搜索的伪代码和事例：

结点中的x/y表示该结点的发现时间为x，完成时间为y
图中树边被标记为灰色，向前，横向，向前的边分别被标记为B, C, F

深度优先搜索的性质

括号花定理

如上图b所示，每个结点的发现时间和完成时间组成一个括号花结构。

对于两个结点u和v，如果区间[u.d, u.f] 和 [v.d, v.f] 不相交，则u不是v的后代，v也不是u的后代；
如果[u.d, u.f] 包含在 [v.d, v.f] 内，则u是v后代，反之亦然。

白色路径定理

如果结点v是u的后代，当u.d时间时，存在一条从u到v全部由白色结点组成的路径。

拓扑排序

对于有向无环图$G = (V, E)$，其拓扑排序是G种所有结点的一种线性次序，该次序满足如下条件：如果G包含边(u, v)，则结点u在拓扑排序中处于结点v的前面。

许多实际应用都需要使用有向无环图来说明事件的优先次序。

下图是一个穿衣服的实例，图a中表示了穿戴某一件衣物的依赖关系，图b是图a拓扑排序的结果，按照图b相反的顺序穿衣服就是没问题的了。

拓扑排序的思想为：对图G做DFS，然后按照结点搜索的完成时间逆序排序。伪代码如下：

拓扑排序的正确性：在向无环图中，如果有变(u, v)，那么v肯定比u先完成搜索。

强联通分量

有向图$G = (V, E)$的强连通分量是一个最大结点集合$C \subseteq V$，对于该集合的任意一对结点可以互相到达。

下图a的灰色覆盖区域就是图的强联通分量。

算法伪代码如下：

1. 对G做DFS，并记下每个结点的完成时间u.f
2. 转置G，得到$G^T$，如上图b
3. 按照u.f大小，从大到小对$G^T$做DFS
4. 第三步得到的深度优先深林中，每棵深度优先树的结点都组成为G的一个强联通分量

思想：
  对于分量图$G^{SCC} = (V^{SCC}, E^{SCC})$，$V^{SCC} = {v_1, v_2, ... , v_k}$，图$G$中的强联通分量$C_i$集合代表分量图中的结点$v_i$：如果有$x\in C_i, y\in C_j$，且图$G$中有边$(x, y)$，则边$(v_i, v_j) \in E^{SCC}$，且图$G^{SCC}$是有向无环图。

证明：
  引理1：$C$和$C^\prime$是图$G$的两个强连通分量。当$u, v \in C; u^\prime, v^\prime \in C^\prime$， 若有$u \rightsquigarrow u^\prime$，则不可能有$v^\prime \rightsquigarrow v$。
     可用反证法证明，若有$u \rightsquigarrow u^\prime$且$v^\prime \rightsquigarrow v$，则$C$和$C^\prime$将成为同一个强连通分量。
  引理2：$C$和$C^\prime$是图$G$的两个强连通分量。当$(u, v) \in E$且$u \in C, v \in C^\prime$，则$f(C) > f(C^\prime)$
     当$d(C) < d(C^\prime)$时，若$x$为$C$中最早被发现的结点，则$C$和$C^\prime$中的其它结点都是$x$的子孙，也就是所有结点的完成时间都比$x$早，所以$x.f=f(C)>f(C^\prime)$
     当$d(C) > d(C^\prime)$时，根据引理1，没有从$C$到$C^\prime$的边，也就是$C^\prime$完成之后不会到达任意$C$中的结点，所以$f(C)>f(C^\prime)$
  引理3：$C$和$C^\prime$是图$G$的两个强连通分量。当$(u, v) \in E^T$且$u \in C, v \in C^\prime$，则$f(C) < f(C^\prime)$
     $(u, v) \in E^T \Longrightarrow (v, u) \in E$，由引理2可直接得知$f(C) < f(C^\prime)$
  证明：根据数学归纳法，假设算法第三行所生成的前$k$棵树都是强连通分量，现在需要考虑第$k+1$棵树是否为强连通分量：
     设第$k+1$棵树是$C$，$C$的根节点为$u$，$u$所在的强连通分量为$C^{\prime\prime}$。
     若$G^T$中从$C^{\prime\prime}$到其他强连通分量$C^{\prime\prime\prime}$有边，那么根据引理3可知$f(C^{\prime\prime}) < f(C^{\prime\prime\prime})$。
     而算法对$G^T$做DFS时，是按照$f$大小逆序进行，所以从$C^{\prime\prime}$出来的变都是到前$k$棵树的。
     所以$C=C^{\prime\prime}$，也就是说第$k+1$棵树为强连通分量。