本章旨在复习初等图论。如果读者之前对图算法有所了解，本章应该足以入门。如果读者没有图算法的背景，我们建议更深入的介绍，例如 Cormen、Leiserson 和 Rivest 的 算法导论。
图是一种数学抽象，可用于解决多种问题。从根本上说，图由一组顶点和一组边组成，其中边是连接图中两个顶点的东西。更准确地说，图是一个对 (V,E)，其中 V 是一个有限集，E 是 V 上的二元关系。V 称为顶点集，其元素称为顶点。E 是边的集合，其中边是一对 (u,v)，其中 u,v 在 V 中。在有向图中，边是有序对，连接源顶点到目标顶点。在无向图中，边是无序对，并在两个方向上连接两个顶点，因此在无向图中 (u,v) 和 (v,u) 是编写同一边的两种方式。
图的定义在某些方面是模糊的；它没有说明顶点或边代表什么。它们可以是连接道路的城市，也可以是带有超链接的网页。从图的定义中省略这些细节是有重要原因的；它们不是图抽象的必要组成部分。通过省略细节，我们可以构建一个可重用的理论，可以帮助我们解决许多不同种类的问题。
回到定义：图是一组顶点和边。为了演示的目的，让我们考虑一个图，其中我们用字母标记了顶点，并将边简单地写成一对字母。现在我们可以写出一个有向图的例子如下
| V = {v, b, x, z, a, y } E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) } G = (V, E) |
图 1 给出了此图的图形视图。边 (x,x) 称为自环。边 (b,y) 和 (b,y) 是平行边，这在多重图中是允许的（但在有向图或无向图中通常不允许）。
接下来我们有一个类似的图，尽管这次是无向的。图 2 给出了图形视图。自环在无向图中是不允许的。此图是前一个图的无向版本（减去平行边 (b,y)），意味着它具有相同的顶点和相同的边，但方向已移除。自环边也已被移除，并且诸如 (a,z) 和 (z,a) 之类的边被折叠为一条边。可以反过来，通过将每条边替换为两条边（一个指向每个方向），来创建一个无向图的有向版本。
现在介绍更多图论术语。如果边 (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 接近 V2 的图是稠密图，而 E = alpha V 且 alpha 远小于 V 的图是稀疏图。对于稠密图，邻接矩阵表示通常是最佳选择，而对于稀疏图，邻接列表表示是更好的选择。边列表表示也是稀疏图节省空间的选择，在某些情况下适用。
图的邻接矩阵表示是一个二维 V x V 数组。数组中的每个元素 auv 存储一个布尔值，说明边 (u,v) 是否在图中。图 3 描述了图 1 中图的邻接矩阵（减去平行边 (b,y)）。存储邻接矩阵所需的空间量为 O(V2)。可以在 O(1) 时间内访问、添加或删除任何边。添加或删除顶点需要重新分配和复制整个图，这是一个 O(V2) 操作。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。交叉边是不属于上述三类的边。
广度优先搜索是一种遍历图的方法，它触及从特定源顶点可达的所有顶点。此外，遍历的顺序是算法将先探索一个顶点的所有邻居，然后再继续探索其邻居的邻居。考虑广度优先搜索的一种方式是，它像从石头 dropped 入水池的波浪一样扩散。同一“波浪”中的顶点与源顶点的距离相同。顶点在算法首次遇到它时被发现。在一个顶点的所有邻居都被探索后，该顶点被完成。这是一个例子，以帮助澄清这一点。图 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，该子集连接图中的所有顶点，并且其总权重最小化，其中总权重由下式给出
图论中的经典问题之一是找到图中两个顶点之间的最短路径。形式上，路径是图 G = (V, E) 中的顶点序列 <v0,v1,...,vk>，使得每个顶点都连接到序列中的下一个顶点（边 (vi,vi+1) 对于 i=0,1,...,k-1 在边集 E 中）。在最短路径问题中，每条边都给出一个实数值权重。因此，我们可以谈论路径的权重
最短路径问题有几种变体。上面我们定义了单对问题，但也存在单源问题（从一个顶点到图中每个其他顶点的所有最短路径），等效的单目的地问题和所有对问题。事实证明，没有解决单对问题的算法比解决单源问题的算法在渐近意义上更快。
图 G=(V,E) 中以顶点 r 为根的最短路径树是有向子图 G'=(V',E')，其中 V' 是 V 的子集，E' 是 E 的子集，V' 是从 r 可达的顶点集，G' 形成以 r 为根的有根树，并且对于 V' 中的所有 v，从 r 到 G' 中的 v 的唯一简单路径是从 r 到 G 中的 v 的最短路径。单源算法的结果是一棵最短路径树。
流网络是一个有向图 G=(V,E)，具有一个源顶点 s 和一个汇顶点 t。每条边都有一个正实值容量函数 c，并且在每个顶点对上都定义了一个流函数 f。流函数必须满足三个约束
f(u,v) <= c(u,v) 对于所有 (u,v) 在 V x V 中 （容量约束）
f(u,v) = - f(v,u) 对于所有 (u,v) 在 V x V 中 （斜对称性）
sumv 在 V 中 f(u,v) = 0 对于所有 v 在 V - {s,t} 中 （流量守恒）
网络的流是流入汇顶点 t 的净流量（等于离开源顶点 s 的净流量）。
|f| = sumu 在 V 中 f(u,t) = sumv 在 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| 的最大可能值以及图中每对顶点的相应流值。
最小成本最大流问题是确定最大流，该最大流使 sum(u,v) 在 E 中 cost(u,v) * f(u,v) 最小化。
流网络在 图 8 中显示。顶点 A 是源顶点，H 是目标顶点。
解决最大流问题的算法有着悠久的历史，第一个算法归功于 Ford 和 Fulkerson。迄今为止，最好的通用算法是 Goldberg 的 push-relabel 算法，该算法基于 Karzanov 引入的预流的概念。
给定一个无向图 G = (V, E)，G 的割是将顶点划分为两个非空集合 X 和 
。割的权重定义为集合 X 和 
之间边的数量（如果 G 是未加权的），或者集合 X 和 之间所有边的权重之和（如果 G 是加权的，每条边都有一个关联的非负权重）。
当割 
的权重对于图 G 最小（即，G 的没有其他割具有更小的权重）时，则该割被称为最小割或 min-cut。例如，给定这个加权图
割 {{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。
| 版权所有 © 2000-2001 | Jeremy Siek, 印第安纳大学 (jsiek@osl.iu.edu) |
