图问题：多项式时间算法

### 图问题：多项式时间算法 #### 1. 引言 算法图问题约占所有问题的三分之一，许多其他领域的问题也可以用图来表述，如带宽最小化和有限状态自动机优化。识别图论不变量或问题的名称是优秀算法学家的基本技能。本文将介绍一些存在高效算法的图问题，这些算法的运行时间随图的规模呈多项式增长，通常用 \(n\) 表示图的顶点数，\(m\) 表示边数。 图通常可以通过绘图来理解，一些有趣的图性质与特定类型的绘图有关，如平面图。此外，还会讨论图、树和平面图的绘制算法。虽然大多数高级图算法编程难度较大，但如果知道从哪里寻找，还是可以找到不错的实现，如 LEDA 和 Boost Graph Library。 以下是一些关于图算法的书籍推荐： - Sedgewick：对该领域进行了全面且易懂的介绍。 - Ahuja, Magnanti, and Orlin：虽名为网络流书籍，但涵盖了广泛的图算法，强调运筹学应用，强烈推荐。 - Gibbons：包含图算法的诸多内容，如平面性测试、匹配、欧拉/哈密尔顿循环等。 - Even：一本较老但仍受尊重的高级图算法教材，对平面性测试算法有深入讲解。 #### 2. 连通分量 - **输入描述**：有向或无向图 \(G\)。 - **问题描述**：识别图 \(G\) 的不同部分或分量，若图中顶点 \(x\) 到 \(y\) 不存在路径，则 \(x\) 和 \(y\) 属于不同分量。 连通分量代表图的各个部分，两个顶点在同一分量中当且仅当它们之间存在路径。寻找连通分量是许多图应用的核心，例如在识别一组物品的自然簇时，可将每个物品用顶点表示，相似物品对之间添加边，图的连通分量就对应不同类别的物品。 测试图的连通性是每个图算法的重要预处理步骤，在不连通图的单个分量上运行算法可能会导致难以检测的细微错误。对于无向图，可使用深度优先搜索（DFS）或广度优先搜索（BFS）来测试连通性，两种方法均可将每个顶点的分量编号初始化为 0，从顶点 \(v_1\) 开始搜索分量 1，发现每个顶点时将其分量编号设置为当前分量编号。初始遍历结束后，增加分量编号，从分量编号仍为 0 的第一个顶点开始新的搜索。使用邻接表正确实现时，时间复杂度为 \(O(n + m)\)。 在实际应用中，还会出现其他连通性概念： - **有向图的连通性**：有向图有弱连通和强连通两种不同的连通分量概念。忽略边的方向后连通的有向图为弱连通图；任意两个顶点之间都存在有向路径的有向图为强连通图。测试有向图的弱连通性可将所有边变为无向边，然后使用基于 DFS 的连通分量算法；测试强连通性则较为复杂，最简单的线性时间算法是从某个顶点 \(v\) 开始搜索，证明整个图可从 \(v\) 到达，然后反转图 \(G\) 的所有边得到 \(G'\)，从 \(v\) 遍历 \(G'\) 以确定 \(G\) 的所有顶点是否都能到达 \(v\)。也可使用更复杂的基于 DFS 的算法在线性时间内提取所有强连通分量，具体步骤如下： 1. 从图 \(G\) 中的任意顶点开始进行 DFS，并按完成顺序（而非发现顺序）标记每个顶点。 2. 反转图 \(G\) 中每条边的方向，得到 \(G'\)。 3. 从 \(G\) 中编号最高的顶点开始对 \(G'\) 进行 DFS，如果此次搜索未完全遍历 \(G'\)，则从编号最高的未访问顶点继续。 4. 步骤 3 中创建的每个 DFS 树都是一个强连通分量。 - **图/网络的薄弱点**：图的连通性衡量其强度，即需要移除多少条边或顶点才能使其断开。双连通分量是通过切断单个顶点的关联边得到的图的部分，可使用 DFS 在线性时间内找到所有双连通分量。 - **图是否为树及寻找环**：对于无向图，树是无环的连通图，可使用深度优先搜索测试其连通性，若图连通且 \(n\) 个顶点有 \(n - 1\) 条边，则为树。深度优先搜索可用于在有向和无向图中寻找环，在 DFS 中遇到回边（指向 DFS 树中祖先顶点的边）时，回边和树一起定义了一个有向环。无环的有向图称为有向无环图（DAG），拓扑排序是 DAG 上的基本操作。 以下是一些实现连通分量算法的库： | 语言 | 库名称 | 支持的算法 | | ---- | ---- | ---- | | C++ | Boost Graph Library | 连通分量、强连通分量 | | C++ | LEDA | 连通分量、强连通分量、双连通和三连通分量、BFS、DFS | | Java | JUNG | 双连通分量算法 | | Java | JGraphT | 强连通分量 | #### 3. 拓扑排序 - **输入描述**：有向无环图 \(G = (V, E)\)，也称为偏序集。 - **问题描述**：找到顶点 \(V\) 的线性排序，使得对于每条边 \((i, j) \in E\)，顶点 \(i\) 在顶点 \(j\) 的左侧。 拓扑排序是大多数有向无环图算法中的子问题，它以简单一致的方式对 DAG 的顶点和边进行排序，类似于深度优先搜索在一般图中的作用。拓扑排序可用于在优先级约束下安排任务，将任务用顶点表示，任务之间的优先级约束用边表示，任何拓扑排序（线性扩展）都定义了一个任务执行顺序，使得每个任务在其所有约束条件都满足后才执行。 拓扑排序有以下重要事实： - 只有 DAG 可以进行拓扑排序，因为有向环会导致任务线性顺序的内在矛盾。 - 每个 DAG 都可以进行拓扑排序，因此对于任何合理的任务优先级约束，至少存在一种调度方案。 - DAG 通常可以有多种不同的拓扑排序方式，尤其是在约束较少的情况下，例如 \(n\) 个无约束任务的 \(n!\) 种排列都是有效的拓扑排序。 概念上最简单的线性时间拓扑排序算法是对 DAG 进行深度优先搜索，识别所有入度为 0 的源顶点，源顶点可以放在任何调度的开头而不违反任何约束。删除这些源顶点的所有出边会产生新的源顶