基础图论回顾

本章旨在复习基础图论。如果读者之前对图算法有所了解，本章应该足以入门。如果读者之前没有接触过图算法，我们建议阅读更全面的介绍，例如 Cormen、Leiserson 和 Rivest 的《算法导论》。

图抽象

图是一种数学抽象，可用于解决多种问题。从根本上来说，图由一组顶点和一组边组成，其中边是连接图中两个顶点的东西。更准确地说，图是一对 $(V,E)$，其中 $V$ 是有限集，$E$ 是 $V$ 上的二元关系。$V$ 称为顶点集，其元素称为顶点。$E$ 是边的集合，其中边是一对 $(u,v)$，$u,v$ 在 $V$ 中。在有向图中，边是有序对，连接着源顶点和目标顶点。在无向图中，边是无序对，并且在两个方向上连接两个顶点，因此在无向图中 $(u,v)$ 和 $(v,u)$ 是同一条边的两种写法。

图的定义在某些方面是模糊的；它没有说明顶点或边代表什么。它们可以是有道路相连的城市，也可以是带有超链接的网页。这些细节被排除在图的定义之外有一个重要原因：它们不是图抽象的必要部分。通过省略细节，我们可以构建一个可重用的理论，它可以帮助我们解决许多不同类型的问题。

回到定义：图是一组顶点和边。作为演示，让我们来考虑一个图，其中我们用字母标记了顶点，并且将一条边简写为一对字母。现在我们可以写出一个有向图的例子，如下：

$$
\begin{aligned}
& V = \{ \space v, \space b,\space x,\space z,\space a,\space y\space \} \\
& E = \{ \space (b,\space y),\space (b,\space y),\space (y,\space v),\space (z,\space a),\space (x,\space x),\space (b,\space x),\space (x,\space v),\space (a,\space z)\space \} \\
& G = (V, E)\\
\end{aligned}
$$

图 1 给出了该图的示意图。边 $(x,x)$ 称为自循环。边 $(b,y)$ 和 $(b,y)$ 是平行边，在多重图中允许（但在有向或无向图中通常不允许）。

接下来我们有一个类似的图，这次它是无向的。图 2 给出了示意图。无向图中不允许自循环。该图是上一个图的无向版本（减去平行边 $(b,y)$），这意味着它具有相同的顶点和相同的边，但方向已被删除。此外，自环边也被删除，并且诸如 $(a,z)$ 和 $(z,a)$ 之类的边被折叠为一条边。也可以采用另一种方式制作无向图的有向版本，将每条边替换为两条边，分别指向每个方向。

$$
\begin{aligned}
& V = \{ \space v, \space b,\space x,\space z,\space a,\space y\space \} \\
& E = \{ \space (b,\space y),\space (y,\space v),\space (z,\space a),\space (b,\space x),\space (x,\space v) \} \\
& G = (V, E) \\
\end{aligned}
$$

现在来看一些别的图论术语。如果某条边 $(u,v)$ 在图 $G$ 中，则顶点 $v$ 与顶点 $u$ 相邻。在有向图中，边 $(u,v)$ 是顶点 $u$ 的出边和顶点 $v$ 的入边。在无向图中，边 $(u,v)$ 与顶点 u 和 v 相关联。

在图 1 中，顶点 $y$ 与顶点 $b$ 相邻（但 $b$ 与 $y$ 不相邻）。边 $(b,y)$ 是 $b$ 的出边和 $y$ 的入边。在图 2 中，$y$ 与 $b$ 相邻，反之亦然。边 $(y,b)$ 与顶点 $y$ 和 $b$ 相关联。

在有向图中，顶点的出边数是其出度，入边数是其入度。对于无向图，入射到顶点的边的数量就是它的度。在图 1 中，顶点 $b$ 的出度为 3，入度为零。在图 2 中，顶点 $b$ 的度数仅为 2。

路径是图中的一系列边，它们使得每条边的目标顶点是序列中下一条边的源顶点。如果存在一条从顶点 $u$ 开始并在顶点 $v$ 结束的路径，我们说 $v$ 可以从 $u$ 到达。如果序列中没有重复的顶点，则路径是简单的。路径 $<(b,x),(x,v)>$ 很简单，而路径 $<(a,z),(z,a)>$ 则不然。另外，路径 $<(a,z), (z,a)>$ 称为循环，因为路径中的第一个顶点和最后一个顶点相同。没有循环的图是非循环的。

平面图是可以在平面上绘制且没有任何边相互交叉的图。平面图的面是由边包围的平面的连通区域。平面图的一个重要属性是面、边和顶点的数量满足欧拉公式：$|F| -|E| + |V| = 2$。这意味着一个简单的平面图最多有 $O(|V|)$ 条边。

图数据结构

在决定使用哪种数据结构时要考虑的图的主要属性是稀疏性，即图中边的数量相对于顶点的数量。$E$ 接近 $V^2$ 的图是稠密图，而 $E = alpha V$ 并且 $alpha$ 远小于 $V$ 的图是稀疏图。对于稠密图，邻接矩阵表示通常是最佳选择，而对于稀疏图，邻接链表表示是更好的选择。此外，边列表表示对于稀疏图来说是一种节省空间的选择，在某些情况下是合适的。

邻接矩阵表示法

图的邻接矩阵表示是一个二维 $V \times V$ 数组。数组 $a_uv$ 中的每个元素都存储一个布尔值，表示边 $(u,v)$ 是否在图中。图 3 描绘了图 1 中的图的邻接矩阵（减去平行边 $(b,y)$）。存储邻接矩阵所需的空间量为 $O(V^2)$。任何边都可以在 $O(1)$ 时间内访问、添加或删除。添加或删除顶点需要重新分配和复制整个图，这是一个 $O(V^2)$ 操作。adjacency_matrix 类是根据邻接矩阵数据结构实现 BGL 图接口。

邻接链表表示法

图的邻接链表表示存储每个顶点的出边序列。对于稀疏图，这可以节省空间，因为只需要 $O(V + E)$ 内存。此外，可以更有效地访问每个顶点的出边。边插入的时间复杂度为 $O(1)$，但访问任何给定边的时间复杂度为 $O(alpha)$，其中 $alpha$ 是矩阵的稀疏因子（等于图中任何顶点的出边的最大数量）。图 4 描述了图 1 中的图的邻接链表表示。adjacency_list 类是邻接链表表示的实现。

边链表表示法

图的边列表表示只是一个边序列，其中每条边都表示为一对顶点 ID。所需的内存仅为 $O(E)$。边插入通常是 $O(1)$，但访问特定边是 $O(E)$（效率不高）。图 5 显示了图 1 中的图的边列表表示。edge_list 适配器类可用于创建边链表表示的实现。

图算法

图搜索算法

树边是通过在图上运行图搜索算法（隐式或显式）构建的搜索树（或森林）中的边。如果 $v$ 是在搜索（对应于访问子 explore() 方法）边 $(u,v)$ 时首次发现的，则边 $(u,v)$ 是树边。后续边是将顶点连接到搜索树中的祖先。因此，对于边 $(u,v)$，顶点 $v$ 必须是顶点 $u$ 的祖先。前向边是将搜索树中的顶点 $u$ 连接到后代 $v$ 的非树边 $(u,v)$。交叉边是不属于上述三类的边。

广度优先搜索

广度优先搜索是对图的遍历，该图从特定源顶点触及所有可达顶点。此外，遍历的顺序使得算法将先探索顶点的所有邻居，然后再继续探索其邻居的邻居。思考广度优先搜索的一种方式是，它会像一块石头落入水池中发出的波浪一样扩展。同一“波”中的顶点距源顶点的距离相同。算法第一次遇到顶点时就会发现它。当一个顶点的所有邻居都被探索完之后，它就完成了。这里有一个例子可以帮助阐明这一点。图 6 显示了一个图，下面显示了顶点的 BFS 发现和完成顺序。

order of discovery: s r w v t x u y
order of finish   : s r w v t x u y

我们从顶点 $s$ 开始，首先访问 $r$ 和 $w$（$s$ 的两个邻居）。一旦 $s$ 的两个邻居都被访问，我们就访问 $r$ 的邻居（顶点 $v$），然后访问 $w$ 的邻居（$r$ 和 $w$ 之间的发现顺序无关紧要），即 $t$ 和 $x$。最后我们访问 $t$ 和 $x$ 的邻居，即 $u$ 和 $y$。

为了让算法跟踪它在图中的位置以及接下来要访问哪个顶点，BFS 需要对顶点进行着色（有关将属性附加到图的更多详细信息，请参阅属性映射部分）。放置颜色的位置可以在图的内部，也可以作为参数传递到算法中。

深度优先搜索

深度优先搜索 (DFS) 访问图中的所有顶点。当选择接下来要探索的边时，该算法总是选择“更深入”地进入图。也就是说，它将选择下一个相邻的未访问顶点，直到到达没有未访问的相邻顶点的顶点。然后，算法将回溯到前一个顶点，并继续沿着该顶点尚未探索的边。在 DFS 访问完来自特定源顶点的所有可到达顶点之后，它选择剩余的未发现顶点之一并继续搜索。此过程创建一组深度优先树，它们一起形成深度优先森林。深度优先搜索将图中的边分为三类：树边、后边以及前向或交叉边（未指定是哪一类）。对于给定的图，通常有许多有效的深度优先森林，因此有许多不同的（且同样有效的）方法来对边进行分类。

深度优先搜索的一个有趣的特性是每个顶点的发现和完成时间形成括号结构。如果我们在发现顶点时使用左括号，在完成顶点时使用右括号，那么结果就是一组正确嵌套的括号。图 7 显示了应用于无向图的 DFS，其中边按照探索的顺序进行标记。下面我们列出了按发现和完成时间排序的图的顶点，并显示了括号结构。DFS 被用作其他几种图算法的内核，包括拓扑排序和两种连通分量算法。它还可用于检测循环（请参阅文件依赖项示例的循环依赖项部分）。

order of discovery: a b e d c f g h i
order of finish   : d f c e b a i h g
parenthesis: (a (b (e (d d) (c (f f) c) e) b) a) (g (h (i i) h) g)

最小生成树问题

最小生成树问题定义如下：找到 $E$ 的一个非循环子集 $T$，它连接图中的所有顶点，并且其总权重最小化，其中总权重由下式给出：

$w(T) = T 中所有边 (u,v) 的权重 w(u, v) 的和$

$T$ 被称为最小生成树。

最短路径算法

图论中的经典问题之一是找到图中两个顶点之间的最短路径。形式上，路径是图 $G = (V, E)$ 中的一系列顶点 $<v0,v1,…,vk>$，使得每个顶点都连接到序列中的下一个顶点（边 $(vi,vi +1)$ 对于 i=0,1,…,k-1 位于边集 $E$） 中。在最短路径问题中，每条边都被赋予实值权重。因此我们可以讨论路径的权重

$w(p) = sum of w(vi-1,vi) for i=1..k$

从顶点 $u$ 到 $v$ 的最短路径权重为

$delta (u,v) = min { w(p) : u –> v } if there is a path from u to v$
$delta (u,v) = infinity otherwise$

最短路径是路径权重等于最短路径权重的任何路径。最短路径问题有多种变体。 上面我们定义了单对问题，但还存在单源问题（图中从一个顶点到每个其他顶点的所有最短路径）、等效的单目的地问题和全对问题。事实证明，解决单对问题的算法没有比解决单源问题的算法渐近更快的。

图 $G=(V,E)$ 中以顶点 $r$ 为根的最短路径树是有向子图 $G’=(V’,E’)$，其中 $V’$ 是 $V$ 的子集，$E’$ 是 $E$、$V$ 的子集 ‘ 是从 $r$ 可到达的顶点集，$G’$ 形成以 $r$ 为根的有根树，并且对于 $V’$ 中的所有 $v$，$G’$ 中从 $r$ 到 $v$ 的唯一简单路径是 $G$ 中从 $r$ 到 $v$ 的最短路径。 单源算法的结果是最短路径树。

网络流算法

网络流是一个有向图 $G=(V,E)$，具有源顶点 $s$ 和汇顶点 $t$。 每条边都有一个正实值容量函数 $c$，并且在每个顶点对上定义了一个流函数 $f$。 流函数必须满足三个约束：

$f(u,v) <= c(u,v) for all (u,v) in V x V (Capacity constraint)$
$f(u,v) = - f(v,u) for all (u,v) in V x V (Skew symmetry)$
$sumv in V f(u,v) = 0 for all v in V - {s,t} (Flow conservation)$

网络的流量是进入汇点 $t$ 的净流量（等于离开源顶点 $s$ 的净流量）。

$|f| = sumu in V f(u,t) = sumv in V f(s,v)$

边的剩余容量为 $r(u,v) = c(u,v) - f(u,v)$。$r(u,v) > 0$ 的边是残差边 $Ef$，产生残差图 $Gf = (V, Ef)$。$r(u,v) = 0$ 的边是饱和的。

最大流问题是确定 $|f|$ 的最大可能值以及图中每个顶点对对应的流量值。

最小成本最大流量问题是确定使 $E cost(u,v) * f(u,v)$ 中的 $sum(u,v)$ 最小化的最大流量。

流网络如图 8 所示。顶点 $A$ 是源顶点，$H$ 是目标顶点。

解决最大流问题的算法有着悠久的历史，第一个算法是由 Ford 和 Fulkerson 提出的。 迄今为止最好的通用算法是 Goldberg 的推送重新标记算法，该算法基于 Karzanov 引入的预流概念。

最小分割算法

无向图

给定无向图 $G = (V, E)$，$G$ 的割是将顶点划分为两个非空集合 $X$ 和 $\overline{X} = V - X$。割的权重定义为 如果 $G$ 未加权，则为集合 $X$ 和 $\overline{X}$ 之间的边数，或者如果 $G$ 被加权，则集合 $X$ 和 $\overline{X}$ 之间的所有边的权重之和（每条边都有一个关联的非负权重） ）。

当割集 $C = {X, \overline{X}}$ 的权重对于图 $G$ 来说是最小的（即 $G$ 中没有其他割集具有更小的权重）时，则该割集称为最小割集或最小切割。 例如，给定这个加权图：

切割 {{0, 6}, {3, 2, 7, 1, 5, 4}} 的权重为 13：

最小割为 {{0, 1, 4, 5}, {2, 3, 6, 7}}（权重 4）：

与此示例不同，图有时会有多个最小割，且所有割的权重相等。最小切割算法确定其中之一以及最小切割权重。

有向图

给定有向图 $G = (V, E)$，$G$ 的割是将顶点划分为两个非空集合 $S$ 和 $T$，其中 $S$ 称为源顶点集合，$T$ 称为源顶点集合下沉顶点。 割的容量 $C = (S, T)$ 是从 $S$ 中的顶点到 $T$ 中的顶点（如果 $G$ 未加权）的边数，或者是从 $S$ 中的顶点到 $T$ 中的顶点的边的权重之和（如果） $G$ 已加权。

当有向图的一个割 $C = (S, T)$ 的容量最小时（即 $G$ 中没有其他割具有更小的容量），则 $C$ 称为最小割或 min-cut。

例如，给定这个有向图：

最小切割是：

其中 $S = \{0\}, T = \{1,2,3\}$，最小割容量为 1。