【读书笔记】数据结构与算法分析 - C 语言描述 - 第五部分 - 图算法

2022/05/02    74 min read

第十七章 图的性质

• 图的定义：元素的集合 + 元素之间连接的集合
• 图论是组合数学的一个主要分支
• 图的应用例子：地图；超文本；电路；调度；事务；匹配；网络；程序结构
• 任何链式结构都是图的一种表示
• 树和链表的算法都是图算法的特例
• 算法的开销：元素集性质 + 连接集性质
• 术语：
  • 图：顶点集 + 边集
  • 约定：V：顶点数；E：边数
  • 边将一对不同的顶点连接在一起，每对顶点间至多有一条边连接
  • 重复边（平行边）：每对顶点间可有任意边相连（多重图）
  • 自环：顶点连接到自身的边
  • 简单图：无重复边 + 无自环
  • 带自环的多重图
  • 边数：V 个顶点至多有 V(V-1)/2 条边
  • 称谓：
    • 点：顶点、结点（数据结构）
    • 边：边、链接（数据结构）、弧
  • 关系：
    • 一条边连接两个顶点
    • 两个顶点是相互邻接的：A、B 相互邻接
    • 这条边是依附于这两个顶点的：C 依附于 A、B
  • 顶点的度：依附于这个顶点的边数
  • 子图：原图的边子集 + 顶点子集组成的图
  • 导出子图：
  • 绘图：把顶点放在平面上，并画出边
    • 约束：边不相交
  • 平面图：能在平面上画出的，且边不相交的图
  • 欧几里得图：距离相关的图
  • 图同构：有两个图，改变其中一个图的顶点编号后的边集与另一个图相同
    • 对于顶点编号有 V! 种可能
  • 路径：顶点的序列，其中相邻的顶点在图中也是相邻接的
    • 简单路径：顶点和边都不相同
      • 环：第一个顶点和最后一个顶点相同，且为简单路径
    • 回路：第一个顶点和最后一个顶点相同，但不必是简单路径
      • 周游路径：包含图中所有顶点的回路
    • 长度：边数
    • 不相交的：
      • 顶点不相交：两条简单路径除端点外无公共顶点
      • 边不相交：没有公共边
  • 连通图：任意顶点到任意顶点都有路径
    • 不连通的图由数个连通分量组成
    • 最大连通分量：在该子图中的顶点没有到图中其它顶点的路径
  • 树：无环连通图
  • 森林：树的集合
  • 生成树（连通图）：子图中包含所有顶点，且是一棵树
  • 生成森林（图）：子图中包含所有顶点，且是一个森林
  • 图是树的条件：各为充分必要条件
    • 有 V-1 条边，且无环
    • 有 V-1 条边，且连通
    • 每对顶点间只有一条简单路径
    • 图连通，但删除任意边后就不连通了
  • 完全图：所有顶点与所有顶点间均有边相连
  • 补图：完全图 - 原图（边相减，顶点不变）
  • 图的并集：边集的并集导出
  • 任意有 V 个顶点的图都是有 V 个顶点的完全图的子图
  • 有 V 个顶点的图形式共有 2^{V(V-1)/2} 种
  • 团：一般图中出现的完全图子图
  • 图的稠密度：平均顶点度：2E/V
  • 稠密图：平均顶点度与 V 成正比：E 与 V^2 成正比
  • 稀疏图：补图为稠密图的图
  • 二分图：顶点分为两个集合，任意边依附的顶点来自不同的集合
    • 递归：任何子图也是二分图
  • 有向图：边是单向的，顶点对是有序的（不能任意调换位置）
    • 有向边：箭头表示：v->w
      • 第一个顶点：源点（头，head）
      • 第二个顶点：目的点（尾，tail）
    • 顶点：
      • 入度：进入该点的边数（以该点为目的点的边数）
      • 出度：离开该点的边数（以该点为源点的边数）
    • 有向环
    • 有向无环图（DAG）
    • 潜在无向图：边可以解释为是无向的
  • 加权图（网）：边关联权值或顶点关联权值，可有多个权值
• 图的 ADT：
  • 静态图：有固定的顶点和边
  • 动态图：图处理时会有边或顶点的插入和删除：在线算法（动态算法）
  • 任务：
    • 计算图中某个度量的值：连通分量数；最短路径
    • 计算图中某个边子集：生成树；含给定顶点的最长环
  • 图表示的要求：
    • 包含应用中的图类型（不愿意浪费空间）
    • 有效构造所需的数据结构
    • 算法不过度受到表示的约束
  • 邻接矩阵：稠密图：E 与 V^2 成正比
  • 邻接表：稀疏图：与 V+E 相比来说 V^2 很大
• 边数组：

• 邻接矩阵表示：
  • 定义：
    • V*V 的布尔数组，有权值时为整数数组
    • 二维数组
    • 有 v-w 这条边时，v 行 w 列值为 1
    • 空间：V^2
  • 无向图时是对称的，可以根据这个特性来节省空间
  • 自动不允许平行边，其它表示时不允许平行边需要很大的开销
  • 使用的理由：
    • V^2 很小，使表示的时间可被忽略
    • 算法多于 V^2 步
• 邻接表表示：
  • 定义：
    • 将在图中与某顶点邻接的顶点都放入一条链表中
    • 使用链表数组，给定顶点可访问到那条链表
  • 链表的特点：增加新边只需常量时间
  • 空间：与 V+E 成正比
  • 检查重复边需搜索链接表，与 V 成正比
  • 删除边：与 V 成正比
  • 链表中元素顺序有异
  • 改进：常量时间的删除边和平行边检测
  • 缺点：检查边与 V 成正比
  • 符号表：常量查找边
  • 变长数组（大型静态表）
• 变量、扩展和开销：
  • 改进：
    • 扩展基本结构可表示其它类型的图
    • 修改或增大数据结构使某些操作更高效
  • 检测 v 的度是否为 0：
    • 邻接矩阵：每行每列与 v 对应的元素
    • 邻接表：adj[v]
    • 边数组：所有 E 边
    • 顶点索引数组可以常量时间
• 边数组、邻接矩阵和邻接表开销：

• 图生成器：
  • 随机图生成器：
    • 随机边：出现大量自环和平行边，适合稀疏图
    • 随机图：排除了重复边，边数不准确，适合稠密图
  • 图的类型：K-近邻图；欧几里得近邻图；事务图；函数调用图；分离度图；区间图；de Bruijn 图
• 简单路径、欧拉路径和哈密顿路径：
  • 找出连接两个给定顶点的一条路径：线性
  • 图算法中线性代表：在图规模 V+E 的一个常量因子内
  • 哈密顿路径：给定两个顶点有一条简单路径，且访问图中所有顶点一次
    • 哈密顿回路问题：从顶点又回到自身
    • 最坏：指数
  • 欧拉路径：给定两个顶点有一条路径访问图中所有边一次（路径可非简单路径，顶点可访问多次）
    • 欧拉回路：从顶点又回到自身，图连通，且所有顶点为偶数度数
    • 欧拉路径：图连通，且只有两个顶点为奇数度数
    • 直接递归实现：阶乘
    • 可达到线性
• 图处理问题：
  • 简单（容易）：可用某种精致而有效的小程度解决
    • 简单连通性；有向图中的强连通性；传递闭包；最小生成树；单顶点最短路径
  • 易解的：时间、空间由图规模（V+E）的一个多项式函数限定
    • 平面性；匹配；有向图中偶环；指派；一般连通性；邮差问题
  • 难解的（NP-难）：无合理时间
    • 最长路径；可着色性；独立集；团
  • 未知的：无高效解，且无法认定为 NP-难问题
    • 图同构

第十八章 图搜索

• 定义：系统地检查图中每个顶点和每条边
• DFS：
  • 解决连通性问题
  • 两种实现：
    • 递归（系统栈）
    • 显式栈
• BFS：
  • 解决最短路径问题
  • 实现：用队列替代 DFS 中的栈
• 探索迷宫：
  • Trémaux 搜索：
    • 步骤 1, 2, 3
    • 可访问所有顶点和边
    • 右手靠墙时，且图中有环路时无法探索整个迷宫
    • 根据通道有 4 种情况：1, 2, 3, 4
• 深度优先搜索：对顶点标记，然后递归地访问与该顶点邻接，且未被访问过的顶点
  • 遇到 v-w 边时：
    • w 未被标记：递归调用
    • w 已被标记：跳过
    • 相反边 w-v：忽略
  • DFS 树（递归调用树）：搜索过程的一种结构性描述
• 图搜索 ADT 函数：
  • 图搜索方法：
    • 从顶点到顶点沿着边行进，目的是为了系统地访问每个顶点每条边
    • 图不连通时（多个连通分量）：每个连通分量调用一次
    • 步骤：
      1. 查找一个未标记的顶点（起始顶点）
      2. 访问包含起始顶点的连通分量重的所有顶点，并标记为已访问
      3. 直至图中所有顶点都被标记为已访问
    • 每条边定量处理：线性或近似线性
  • DFS 运行时间：
    • 邻接矩阵：与 V^2 成正比
    • 邻接表：与 V+E 成正比
    • 与图规模呈线性
  • DFS 函数：基于 DFS 模式的所有实现
  • 使用基于顶点索引的数组：
    • 全局变量：搜集图结构的信息
    • 在图的表示中：计算图信息预处理函数
    • 作为函数参数由客户提供：实现 ADT
  • 标准邻接矩阵 DFS
  • 标准邻接表 DFS
• DFS 森林的性质：
  • DFS 访问结点的顺序与前序遍历树的内部结点的序列相同：图搜索为树遍历的推广
  • 边：检查边等同于访问边
    • 树边：表示递归调用的边
      • 第一次：树链接：w 未被初始化：递归调用
      • 第二次：父链接：st[w] 为 v：忽略
    • 回边：将某顶点与它的 DFS 树中祖先顶点相连的边，且该祖先不是其父结点
      • 第一次：回链接：pre[w] < pre[v]（st[w] != v），pre[] 为前序编号：未完成
      • 第二次：下链接：pre[w] > pre[v]：已完成
  • 连通分量个数 = DFS 森林中树的个数
• DFS 算法：
  • 应用：
    • 环检测：一次 DFS 中无回边或向下边则表示无环
      • 邻接矩阵：与 V^2 成正比；邻接表：与 V 成正比
    • 简单路径：线性
    • 简单连通性：线性，图只调用 DFS 一次
    • 双向欧拉回路
    • 生成树：DFS 树
    • 顶点搜索：顶点计数
    • 2-可着色性、二分图性、奇环：按照层次交替指定颜色，并在着色过程中检查回边是否存在不一致性
• 可分离性和双连通性：
  • 桥（可分离的边）：图中的某条边，当删除它时会让一个连通图分成两个不相交的子图
  • 边连通的图：不含有桥的图：每对顶点由两条边不相交的路径连接，边不相交意味着可由公共点，但不能有公共边
  • 边可分离的图：不是边连通的图
  • 边连通分量（桥连通分量，不含桥的最大子图）：删除一个边可分离的图中的所有桥而得到的分量（子图）
  • DFS 树中的树边 v-w 是桥，当不存在回边时，把 w 的子孙结点和 w 的祖先结点连接起来
  • 识别桥：线性
  • 关结点（分离顶点、切割点）：图中的某个顶点，当删除它时会让一个连通图分成至少 2 个不相交的子图
  • 可分离的：图不是双连通的
  • 顶点连通的图（双连通的图）：
    • 图中每对顶点都有两点不相交的路径
    • 不含关结点的图
    • 顶点连通的图都是边连通的，但边连通的图不一定是顶点连通的
  • 找出关结点和双连通分量：线性
  • 顶点：1 连通 = 连通；2 连通 = 双连通
    • 图是 k 连通的：至少有 k 条不相交的路径连接每对顶点
    • 图的顶点连通度：将图分成 2 部分所要删除的最小顶点数
    • Menger 定理：顶点连通度 = 顶点间顶点不相交路径的最大个数
  • 边：2 边连通 = 边连通
    • 图是 k 边连通的：至少有 k 条边不相交的路径连接每对顶点
    • 图的边连通度：将图分成两部分所需删除的最少边数
  • st 连通性：将 s、t 分离所需删除的最小边数或顶点数
  • 一般连通性：图的边连通度或顶点连通度
• 广度优先搜索：
  • 定义：为了找出从 v 到 w 的一条路径，从 v 开始，对于可以从 v 用 1 条边到达的所有顶点，检查这些顶点是否为 w。不是则检查从 v 用 2 条边到达的顶点，3 条边以此类推。直到找到 w
  • 队列用作边缘集的数据结构
  • 队列中的边将访问过的顶点与未访问过的顶点相连
  • 顶点按照与起始顶点的距离大小进入或离开队列：0, k, k+1
  • 步骤：
    1. 从队列中取边，直到某条边指向一个未被访问过的顶点
    2. 访问该顶点，再将从此顶点到未被访问顶点的所有边放入队列中
    3. 直至队列为空
  • 以 v 为根的 BFS 树，树中某点 w 到 v 的路径对应着图中 v-w 的最短路径
  • 邻接矩阵时：与 V^2 成正比
  • 邻接表时：与 V+E 成正比
  • 应用：
    • 最短路径（点到点）
    • 单源点最短路径（点到所有点）
    • 所有对之间最短路径（对每个点执行单源点）
• 广义图搜索：
  • 边缘集：下一次向树中添加的可能候选边集合
  • 通用方案：将边缘集中的一条边移到树中，访问这条边指向的顶点，并将由该顶点指向未访问顶点的所有边放入边缘集中，在边缘集中使用一种替换策略来保证其中任意两条边都不指向同一顶点
  • 无重复目的顶点：
    • DFS：忘记旧元素的栈
    • BFS：忽略新元素的队列
  • 广义队列（V）+ 替换策略 = 线性访问所有顶点和所有边，空间与 V 成正比
    • 邻接矩阵：与 V^2 成正比 + 最坏情况下 V 次插入、V 次删除、E 次更新
    • 邻接表：与 V+E 成正比 + 最坏情况下 V 次插入、V 次删除、E 次更新
  • 策略：随机队列；优先队列
• 图算法分析：
  • 寻求理然的、自然的输入模型：设计-分析-实现-测试
    • 充分反映实际：大量类型的图
    • 数学分析检验：数学分析有难度，很多基本分析问题尚未定论
    • 生成器、问题实例：无法刻画在实际中出现的图类型
  • 大型的非稀疏随机图很可能是连通的
  • 对于大型稀疏图不应该使用邻接矩阵表示（超大型同样不应该）：初始化数组开销昂贵、算法需要检查数组的每个元素
  • 为大型稀疏图构建邻接表时，为链表结点分配内存的开销很大，为遍历的 5 倍：考虑预先分配数组来降低内存分配的开销
  • 递归 DFS 在图过大时会崩溃：使用非递归版本（栈）
  • 合并-查找快于 DFS 或 BFS：因为它不必表示整个图

第十九章 有向图和无向图

• 有向图中两个顶点有 4 种方式：无边；s->t；t->s；s->t 且 t->s

• 调度问题：完成工作，且不违反优先关系

  • DAG、拓扑排序

• 后面的工作（顶点或边）完成前需要完成前面的：

  • 顶点对应工作
  • 边对应工作：PERT 图

• 环检测；拓扑排序；传递闭包和强连通分量

• 术语和游戏规则：

  • 有向图：顶点集 + 连接有序顶点对的有向边集（不含重复边）
  • 通常约定每个顶点都有一个自环
  • 有向路径：是一个顶点序列，相邻顶点在图中是有边相连的
  • s、t 可达的：存在 s 到 t 的路径
  • 入度：指向该顶点的边数
  • 出度：从该顶点指出的边数
  • 源点：入度为 0 的顶点
  • 汇点：出度为 0 的顶点
  • 求入度、出度、源点、汇点：线性，空间则与 V 成正比
  • 映射：允许自环，且所有顶点出度为 1 的有向图，一个将 0~v-1 上的整数集映射到自身的函数
  • 逆图：由原图所有边上的方向逆转得到
    • 邻接矩阵：转置（交换行和列），如果是不再修改的，就只用交换对行和列的引用
    • 邻接表：
      • 与 E 成正比构建
      • 维护每条边的两种表示（如无向图），且使用额外一位表示方向（可用指针关联这两条边）
  • 有向环：由某个顶点回到其自身的简单有向路径，顶点和边都是不相同的
  • 有向无环图（DAG）：没有有向环的有向图
  • 有向图是强连通的：每个顶点均由每个顶点可达
  • s、t 是强连通的（相互可达的）：s->t 有路径，且 t->s 也有路径：等价关系
  • 环路径：由某个顶点回到其自身的路径，该路径不必是简单地
  • 非强连通有向图的组成：一组强连通分量（强分量）+ 由一个连通分量到另一个连通分量的一组有向边，其中强连通分量就是最大连通子图
  • 核心 DAG：一个由普通有向图转换得来的 DAG，DAG 中每个顶点代表一个强连通分量，顶点间的有向边也对应原图中两个强连通分量中的顶点是否有边相连

• 有向图中的 DFS 剖析：

  • 有向图中树链接与图中的边一一对应：
    • 指向未访问顶点：
      • 树边：递归调用
    • 指向已访问顶点：
      • 回边：顶点到祖先结点：较大后序编号
      • 下边：顶点到子孙结点：较大前序编号
      • 交叉边：顶点到非祖先非子孙结点：较小前序编号
  • 有向环检测（DAG检测）：DFS 时无回边
  • 单源点可达性：DFS 时间与可达顶点导出的子图中边个数成正比

• 可达性和传递闭包：

  • 传递闭包：与原图有相同顶点，当原图中 s、t 有路径是，传递闭包中有边 s->t
    • 布尔矩阵相乘：可使用任何传递闭包算法计算，最多差常数因子（最好V^2.5）有向边
    • 计算传递闭包：
      • 简洁方法（反复平方法）：有邻接矩阵 A，计算 A^V：与 V^3lgV 成正比
      • Warshall 算法：与 V^3 成正比
        • 适合稠密有向图
        • 改进：把对 A[s][i] 的测试从内循环移出
      • 基于 DFS 的传递闭包：时间：与 V(V+E) 成正比，空间：与 V^2 成正比
        • 适合稀疏图
        • 邻接矩阵表示
        • 邻接表表示：对于稀疏图来说最快
      • 抽象传递闭包：测试可达性的 ADT，时间：V^3，空间：V^2
      • Floyd 算法求加权图最短路径

• 等价关系和偏序：

  • 集合中对象的关系：对象的有序对集合
  • 关系与有向图是同一个抽象的不同表示
  • sRt 表示有序对 (s, t) 之间存在关系 R
  • 关系种类：
    • 对称的：sRt 蕴含着 tRs：无向图
    • 自反的：对所有 s 有 sRs：所有顶点均有自环的图
    • 反自反的：对所有 s 没有 sRs：所有顶点均无自环的图
    • 传递的：有 sRt、tRu，则有 sRu
  • 等价关系：自反、对称且传递
    • 示例：模运算；图的连通性
    • 等价类：s \equiv t 表示在同一个等价类中
  • 偏序关系：反自反、非对称和传递
    • 示例：子集包含；DAG 中的路径
  • 全序关系：对于 s != t，有全序 T 为 sTt 和 tTs 只能有一个成立
  • 集合和图模型的对应关系：
    • 关系：有向图
    • 对称关系：无向图
    • 传递关系：图中路径
    • 等价关系：无向图中路径
    • 偏序关系：DAG 中的路径

• 有向无环图：

  • 调度：在约束下完成任务：拓扑排序
    • 约束：所需时间的函数或者任务消耗的其它资源的函数，例如：优先约束：某些任务必须在其它一些任务前执行
  • 树表示压缩成 DAG 表示（动态规划）
  • 二叉树：一个有向无环图，每个结点可发出两条边，且可接受一条边

• 拓扑排序：

  • 目标：处理 DAG 的所有顶点，使得每个顶点在指向的顶点之前被处理
  • 重新编号的拓扑排序
  • 重新排列的拓扑排序，也就是常用的术语拓扑排序，与重新编号的拓扑排序相互可得
  • 产生的顶点顺序非唯一
  • 逆拓扑排序：边从右指向左
    • 可由 DFS 的后序编号而得
    • 正常拓扑排序步骤：
      1. DAG 逆图上进行逆拓扑排序
      2. 栈
      3. 逆序对顶点编号
  • 每个 DAG 至少有一个源点和一个汇点
  • 基于源点队列的重新编号拓扑排序步骤：
    1. 从队列中删除一个源点，并对其标号
    2. 减少某些顶点的入度
    3. 入度为 0 时，将顶点放入源点队列
    4. 直到源点队列为空

• 有向无环图中的可达性：

  • 利用动态规划和 DFS，对于 DAG 的抽象传递闭包
  • 设 X 为 DFS 森林中交叉边的数目：时间：与 V^2+VX 成正比，空间：与 V^2 成正比
  • 稠密 DAG 的传递闭包：最坏 VE，但也有一般情况较快的算法

• 有向图中的强连通分量：

  • DAG 中，s->t 有路径，则 t->s 无路径
  • 强连通分量（强分量）：由相互可达的顶点组成
  • 蛮力算法：使用传递闭包算法，检查每对顶点对 s->t 是否可达，且 t->t 是否可达，将满足此条件的顶点对定义为无向图的一条边，此无向图的连通分量就是原图（有向图）的强分量
  • Kosaraju 算法：
    • 步骤：
      1. 构建逆图，并用 DFS 计算一个后序序列（有向图是 DAG 时为拓扑排序）
      2. 在原图执行 DFS，在调用递归函数的搜索循环中使用由 1 中 DFS 得到后序的逆序：找出搜索的下一个顶点时（可在最外层，也可在递归搜索函数返回给顶层搜索函数时调用递归搜索函数），要使用具有最大后序编号未被访问的顶点
    • 任何图都是线性时间、空间：
      • 稠密图：V^2
      • 稀疏图（邻接表）：V+E
  • Tarjan 算法：
    • 步骤：
      1. 以逆拓扑排序的顺序考虑顶点，从而在到达某个顶点的递归函数末尾时知道，将不会遇到同一个强分量中的任何其它顶点，因为由该顶点可达的所有顶点都已被处理完
      2. 树中的回链接为从一个顶点到另一个顶点提供了第二条路径，并将强分量连在一起
    • 进入递归函数时，将顶点压入栈，在访问某个（多个）强分量的最后一个成员时弹出，并赋予分量编号
    • 识别是否在访问强分量的最后一个成员：通过从每个结点的所有子孙的一个上链接来记录最大可达祖先
    • 线性
    • 有向图
  • Gabow’s 算法：
    • 与 Tarjan 相似，但使用了第二个栈（包含搜索路径中的顶点），而不是 Tarjan 中的顶点索引的前序编号的数组来确定何时从主栈中弹出每个强分量中的顶点
    • 线性
    • 有向图

• 再论传递闭包：

  • 通过有向图来构建核心 DAG 的不同情况：
    • 核心 DAG 相对于原图来说较小：高效
    • 原图是个DAG：无改进
    • 原图与核心 DAG 规模相类似：不会节省很多
    • 原图有大环或大强分量：最优或渐近最优
  • 抽象传递闭包：
    • 适用于任何有向图
    • 原理：
      • 在同一个强分量中时，顶点相互可达
      • 在核心 DAG 中可达，则在原图中也可达
    • 步骤：
      1. 找出其强分量：Kosaraju、Tarjan、Gabow’s
      2. 构建其核心 DAG：对边做一边处理
      3. 计算核心 DAG 的传递闭包：DFS
    • 性能：
      • 计算传递闭包：设 v 为核心 DAG 中顶点数，x 为 DFS 森林中交叉边数，时间：E+v^2+vx，空间：V+v^2
      • 核心 DAG：该核心 DAG 中顶点数少于 \sqrt[3] v，时间：E+V，空间：V

• 展望：

  • 以下均用邻接表表示
  • 有向图开销：

  问题	开销（最坏）	算法
  环检测	E	DFS
  传递闭包	V(E+V)	从每个顶点开始的 DFS
  单源点最短路径	E	DFS
  所有点对最短路径	V(E+V)	从每个顶点开始的 DFS
  强分量	E	Kosaraju、Tarjan、Gabow’s
  传递闭包	E+v(v+x)	核心 DAG

  • DAG 开销：

  问题	开销（最坏）	算法
  环检测	E	DFS或源点队列
  拓扑排序	E	DFS或源点队列
  传递闭包	V(V+E)	DFS
  传递闭包	V(V+X)	DFS或动态规划

  • 动态可达性：合并-查找算法（稠密有向图）
  • 问题：
    • 支配者： DFS 线性
    • 传递归约：易解，如果要求结果限制为原图的子图：NP-难
    • 有向欧拉路径：简单
    • 有向邮差问题：易解，归约到最小成本流
    • 有向哈密顿问题：NP-难，如果有向图为 DAG：简单
    • 单连通子图：NP-难
    • 反馈顶点集：NP-难
    • 偶环：不可用

第二十章 最小生成树

• 图中每条边上关联权值（成本），成本最小化：

  • 最小生成树：所有点连接起来的最小成本
  • 最短路径：两个给定点之间最小成本的路径

• 最小生成树（MST）：

  • 加权图中权值（边上权值之和）不大于任何其它生成树的权值
  • 边上权值可相等：MST 不是唯一的

• 表示：

  • 表示加权图：
    • 可将权值转换为 0-1 之间的实数
    • 不存在的边：
      • 观察哨权值
      • 平行矩阵：两个矩阵，一个指示边是否存在，另一个保存边权值
    • 邻接矩阵：元素为边权值
    • 邻接表：链表元素增加一个表示边权值的域
  • 表示 MST：
    • 图；边链表；边数组；顶点索引的数组（父链接表示）
    • 以上均可在线性时间互相转换

• MST 算法的基本原理：

  • 基础性质：向树中添加一条边会创建一个环（定义树的性质）
  • 图中的割：将顶点分成两个不相交集的一个划分
  • 交叉边：将两个集合中的顶点连接起来的边
  • 割性质：给定图的任意一个割，每条最小的交叉边属于图中的某个 MST，且每个 MST 包含一条最小交叉边
    • 可用作表征 MST 的优化条件
    • 用来识别出在 MST 中的边：接收这条边
  • 环性质：给定一个原图 G，向原图添加一条边后得到图 G’。将某条边添加到原图 G 的一个 MST 中，并删除所得到的环中最大一条边。这样就得到图 G’ 的一个 MST
    • 向一棵生成树不断添加在图中的边，新添加的边需要小于环中的边，从而制造环，并删除环中最大边，直到怎样添加都不能删除。这样就得到一个 MST
    • 用来识别出不在 MST 中的边：拒绝这条边
  • Prim 算法：一次一条边，从任何一个顶点开始，把它作为具有单个顶点的 MST，向它添加 V-1 个顶点，总是取在 MST 中的顶点和不在 MST 中的顶点连接边中的最小边
    • 适合稠密图
  • 反复应用环性质法：向假想 MST 中添加边，如果形成环，则删除环中的最大边
    • 弃用边的难度较大
  • Kruskal 算法：按照边的长度处理边（最短边优先），向 MST 中添加边，不会形成环的边才真正加入 MST 中，在 V-1 条边后停止
  • Boruvka 算法：
    • 步骤：
      1. 向 MST 中添加所有顶点和最近顶点连接起来的边（最小近邻）
      2. 继续向 MST 添加一棵树中的顶点和另一棵树的顶点连接起来的所有边中的最小边（最小近邻）
      3. 直至只剩一棵树
    • 边的权值可相同时：在最小近邻中选择具有最小顶点编号的近邻
  • 抽象操作：
    • 找出连接两棵子树的最小边
    • 确定增加一条边是否会产生一个环
    • 删除环中的最大边

• Prim 算法和优先级优先搜索

  • 描述：维护图的一个割，割由树顶点（在 MST 中的顶点）和非树顶点（不在 MST 中的顶点）组成。从任何在 MST 中的顶点开始，将一条最小交叉边加入到 MST 中（非树顶点变成树顶点），重复 V-1 次，直至所有顶点都在树中
  • 蛮力法：直接可得。选择下一条边的方法：检查从树顶点到非树顶点的所有边中的最小边
  • 增量的变化：只关注由非树顶点到树顶点的最短距离（记录）：
    • V^2，对稠密图来说线性
    • 只检查向树添加顶点后是否需要更新这个最短距离
    • 所需信息：
      • 对于每个树顶点：在 MST 中的父结点；父链接的长度
      • 对于每个非树顶点：最近的树顶点；与树的距离
  • 边缘集：下一次要添加到 MST 中的潜在边集合
  • PFS（广义图搜索）描述：
    • 步骤：
      1. 从边缘集中将一条最小边移到树，并访问该边指向的顶点
      2. 将从该顶点到一个非树顶点的任何边置于边缘集中，如果边缘集中两条边都指向同一个顶点，则用短边取代长边
    • 边缘集为最小优先队列：堆实现时，与 ElgV 成正比
    • 对于任意图和任意优先级函数，在规模至多为 V 的优先队列中，可利用 PFS 找到 MST：线性时间 + V 次插入 + V 次删除最小值 + E 次减少关键字

• Kruskal 算法：

  • 描述：从一个有 V 个单个顶点树的退化森林开始，不断合并两棵树（使用可能的最短边），直至只剩一棵树
  • 经典实现：
    • 步骤：
      1. 按边的权值进行排序，由于权值有限制，可使用基数排序，线性可得，
      2. 使用连通性算法（合并-查找算法）消除导致环的边
    • 开销：ElgE：E 个数排序 + E 次查找 + V-1 次合并
  • 优先队列版本：
    • 线性构造；对数删除最小
    • 开销：E + XlgV，X 为图中不大于 MST 最长边的边数：构造规模为 E 的优先队列 + X 个删除最小 + X 个查找 + V-1 个合并
  • 部分排序版本

• Boruvka 算法：

  • 描述：每步添加数条边到 MST 中，在每一步中，找出连接每棵子树与不同子树的最短边，再将所有这样的边加入 MST 中
  • 连通性算法中的查找函数：为每棵子树关联一个索引，可得知一个给定顶点属于哪棵子树
  • 步骤：
    1. 维护一个顶点索引的数组，对于每个 MST 子树能识别出最近邻
    2. 对图中每条边，边的顶点在同一棵树上时，抛弃；否则检查由该边连接的两棵树之间的最近邻距离，有最近邻则更新距离
    3. 用合并操作将每个顶点与它的最近邻连接起来，然后抛弃目前连通的 MST 子树中连接其它顶点对的所有更长的边
  • O(ElgVlg*E)

• 比较与改进：

  • 稠密图：Prim 算法的邻接矩阵实现经典实现
  • 中等密度图：三种算法皆可，而 Prim 算法的 PFS 实现在取出边的常量因子内
  • 稀疏图：Kruskal 算法，归约为排序（快排）
  • 比较：

  算法	最坏情况	注释
  Prim（标准）	V^2	稠密图最优
  Prim（PFS、堆）	ElgV	保守上界
  Prim（PFS、d-heap）（Johnson 版本）	Elog_dV	除极端稀疏图外都是线性
  Kruskal	ElgE	排序开销占主导
  Kruskal（部分排序）	E+XlgV	开销依赖最长边
  Boruvka	ElgV	保守上界

  • 改进：
    • 更好的优先队列：如斐波那契堆（Fibonacci 堆）：支持常量减小关键字；对数删除最小
    • 优先队列的实现中使用基数方法
    • 用 d-叉堆实现优先队列：支持 log_dV 减小关键字；dlog_dV 删除最小
      • 改进最坏情况
      • 导致 Prim 算法有 Vdlog_dV + Elog_dV，非稀疏图线性

• 欧几里得 MST：

  • 欧几里得 MST 问题：给定平面 N 个点找出连接所有点的最短线段集合：NlgN
    • 构建 N 顶点、N(N-1)/2 条边的完全图，边权值为两点距离：Prim：N^2
    • Delauney 三角的图由 MST，且是一个边数与 N 成正比的平面图。用 NlogN 计算出 Delauney 三角（太复杂）后运行 Kruskal 或 PFS 找出欧几里得 MST
    • 几何算法
    • 基于近邻算法的 Prim 另一版本

第二十一章 最短路径

• 路径权值：那条路径上的边权值之和

• 网（加权有向图）：

  • 网算法同样适用于加权无向图，非加权图也可
  • 自环：表示中保留自环，这样更方便
  • 平行边：可能有平行边，甚至平行边带有不同权值

• 简单有向路径：

  • 正权值边：没必要
  • 负权值边：需要限制为简单路径

• 最短路径：从 s 到 t 的简单有向路径，且不存在有其它更小权值的路径

• 最短路径树（SPT）：定义了从根到其它顶点的最短路径，每条树路径是网中的一条最短路径

• 负环：总权值为负数的有向环

• 源点-汇点最短路径：起始顶点（源点）；完成顶点（汇点）

• 单源点最短路径：找一条最短路径：

  • 最短路径权值
  • 在与长度成正比的时间里追踪路径

• 所有点对最短路径：应用：公路图；航班路线

• 基本原理：

  • 松弛：每步中检查是否可以找到一条比某条已知路径更短的路径
    • 边松弛：检查沿着给定边行进是否会产生到目的顶点的一个新的最短路径
      • 单源点
    • 路径松弛：检查沿着给定边行进是否会产生连接两个其它顶点的一条新的最短路径
      • 所有点对
      • 距离矩阵：d[s][t] 为 s 到 t 的最短路径
      • 路径矩阵：p[s][t] 为 s 到 t 最短路径中 s 的下一个顶点
  • 追踪路径：相反顺序；栈；处理逆图
  • 加号：由边权值计算路径权值
  • 小于号：计算路径权值集中的最小值

• Dijkstra 算法：

  • 定义：从将源点放在 SPT 中开始，然后每次选择一条边构建 SPT，总是选择从源点到不在 SPT 中的一个顶点的最短路径的边
  • 解决非负权值网中的单源点最短路径问题
  • 经典实现适合稠密图，线性，V^2
  • Dijkstra 的 PFS 实现：将连接树顶点与非树顶点的边保存在优先队列，并提供更新优先级的操作
    • 适合稀疏图
    • 用堆来实现优先队列时：ElgV
    • 给定图有 V 个顶点、E 条边、密度 d = E/V：
      • d < 2 时：Dijkstra 时间与 VlgV 成正比
      • 可用 [d]-堆实现优先队列，最坏情况下改进 lg(E/V) 的一个因子：O(Elog_dV)
  • 4 种 PFS 实现：
    • 经典稠密图：Dijkstra、Prim
    • 边缘边集（稀疏图）：教学价值
    • 边缘顶点集（稀疏图）：最优化
    • 所有顶点（稀疏图）：最简单
  • PFS 算法：

  算法	优先级	结果
  DFS	逆前序	递归树
  BFS	前序	SPT（边）
  Prim	边权值	MST
  Djkstra	路径权值	SPT

  • Dijkstra 算法各种实现的开销：

  算法	开销（最坏）	注释
  经典	V^2	稠密图最优
  PFS（完全堆）（所有边）	ElgV	ADT 简单
  PFS（边缘集堆）	ElgV	保守界限
  PFS（d-叉堆）	Elog_dV	除极端稀疏图外，都是线性

• 所有对最短路径：

  • 加权直径：最短路径中最长路径的长度
  • 求所有对最短路径方法：
    • 每个顶点 Dijkstra（非负权值）：
      • 堆：最坏 VElgV VElog_dV
      • d-叉堆：VE，如果 E < 2V，d = 2；否则 d = E/V
      • 适合稀疏图
    • Floyd（可有负权值，但不能有负环）：
      • V^3
      • 适合稠密图

• 无环网中的最短路径：

  • 无环网中：
    • 单源点：线性，与 E 成正比
    • 所有对：与 VE 成正比
    • 最长路径
  • 无环网（加权 DAG）：边上有权值，且不存在环的有向图
  • 单源点：DFS；源点队列
  • 所有点对：每顶点用单源点；单个 DFS。如果加上动态规划就变成拓扑排序，需用逆拓扑排序顺序考虑顶点
  • 多源点最短路径问题（最长）：
    • 使用虚拟顶点把多源点转化成单源点
    • 按照拓扑排序的顺序处理顶点
    • 线性

• 欧几里得网：

  • 定义：边权值为点的几何距离
  • 额外性质：
    • 满足三角不等式：s->d <= s->x + x->d
    • 顶点位置给出了路径长度的一个下界：不存在有 s->d 的路径小于 s->d 的距离
    • 大大减少必须考虑的路径数目
  • 欧几里得启发式搜索：
    • Dijkstra 的 PFS 实现 + 额外性质
    • 重新加权 + 标准最短路径算法
    • 不保证节省
    • A* 算法的特例

• 归约：

  • A 可归约为 B：使用求解 B 的算法去求解 A，最坏时该算法不超过求解 B 算法的常量倍：
    • 转换为 B 的一个实例
    • 求解这个实例
    • 将 B 的解决方案转换为 A 的解决方案
  • 等价：两个问题可相互归约
  • 体现了归约思想：库编程
  • 作用：分类；得到下界
  • 一个问题比另一个问题更一般
  • 传递闭包可归约为非负权值的所有对最短路径
  • 在边权值无限值的网中，单源点（所有点对）的最长路径问题和最短路径问题是等价的
  • 差分约束：为一组遍历 x_0…x_n 赋予非负值，使 x_n 值最小，且满足对一组变量的差分约束
    • 约束指定了两个变量的差必定大于等于一个给定常量
    • 归约为作业调度
    • 正常数时等价于无环网中单源点最长路径问题
  • 线性规划：为一组变量 x_0…x_n 赋予非负值，使变量的特定线性组合达到最小，且满足对变量的一组约束
    • 约束指定了变量的某个线性组合必定大于等于一个给定常量
  • 不可行的：一个没有解决方案的问题实例
  • 具有截止期限的作业调度：归约为可负权值最短路径（不含负环）
  • 一般的最短路径问题、边权值可为负的网的最短路径问题：NP-难
  • 高效：算法最坏时为输入规模的某个多项式函数
  • 难解性：归约为难解性
  • 上界：有 B 的高效算法，且 A 归约为 B，则有 A 的高效算法。可能有 A 的更好算法，但 B 性能是求 A 最佳性能的一个上界
  • 下界：知道 A 的任何算法都有 x 资源需求，且 A 归约为 B，则 B 至少也由 x 资源需求，因为 B 的更好算法蕴含着存在 A 的一个更好算法，也就是说：A 的性能是 B 最佳性能的一个上界
  • 更一般：运筹学（OR）：数学规划

• 负权值：

  • 正权值：寻找捷径
  • 负权值：寻找绕道，尽可能多的负权边：小权值路径比大权值有更多的边
  • 无负环网中的最短路径问题、负环检测：Floyd 算法，对于所有点对 V^2
  • Bellman-Ford 算法：以任意顺序考虑网中的边，并沿着每条边松弛，执行 V 遍
    • 单源点：VE
    • 所有对：V^2E
    • 负环检测：VE
    • 基本方法：对所有边检查
    • 改进：可改变的边为某些顶点发出的边，而这些顶点在上一遍中有所改变：队列
  • 重新加权：将网转换为只有非负权值的网，且有相同的最短路径结构
    • 操作：
      • 边：将该边源点到目的点权值之差加到该边的权值上
      • 网：对所有边重新加权
    • 线性
    • 顶点的权值：最短路径生成森林：为每个顶点赋权（从此根到它在 SPT 中顶点的路径的权值）
      • 从每个强连通分量的一个源点开始
      • 虚拟顶点，与网中每个顶点之间的边权值为 0
  • Johnson 算法：
    • 适用于有负权边，当无负环的网（所有点对）
    • 步骤：
      1. 用 Bellman-Ford 算法找出原网的一个最短路径森林
      2. 有负环则终止
      3. 由最短路径森林对网进行重新加权
      4. 在重新加权后的网上使用所有点对 Dijkstra 算法
    • 所有点对：VElog_dV，如果 E < 2V，则 d = 2；否则 d = E/V

• 展望：

  • 单源点最短路径算法开销：

  权值约束	算法	开销（最坏）	注释
  非负	Dijkstra	V^2	稠密图最优
  非负	Dijkstra（PFS）	ElgV	保守界
  无环	源点队列	E	最优
  不含负环	Bellman-Ford	VE	有改进空间？
  无（一般性问题）	开放问题	？	NP-难

  • 所有点对最短路径算法开销：

  权值约束	算法	开销（最坏）	注释
  非负	Floyd	V^3	对所有网相同
  非负	Dijkstra（PFS）	VElgV	保守界
  无环	DFS	VE	对所有网相同
  不含负环	Floyd	V^3	对所有网相同
  不含负环	Johnson	VElgV	保守界
  无（一般性问题）	开放问题	？	NP-难

第二十二章 网络流

• 最大流问题、最小成本流问题：
  • 配送：商品配送；通信；交通流量
  • 匹配：工作安排；最小距离点匹配
  • 分割：网络可靠性；分割补给性
• 流网络：
  • st 网：有一个指定源点 s 和一个指定汇点 t 的网
    • 指定：忽略指向 s 的边和指出 t 的边
    • 内部结点：除源点和汇点外的其它顶点
    • 表示：每个方向一条边
      • 邻接矩阵：平行数组
      • 邻接表：一条边两种表示中有指针关联
  • 流网络：有正边权值的 st 网，边上权值为容量
    • 边流（流网络中的一个流）：一个非负边（权值）集合
    • 满足：
      • 边流不大于该边容量
      • 进入每个内部顶点的总流量等于从该顶点流出的总流量
      • s 流出量 = t 流入量
    • 顶点：
      • 流入量：进入一个顶点的总流量（该顶点进入边上的流之和）
      • 流出量：流出一个顶点的总流量（该顶点发出边上的流之和）
    • 网的值 = 源点流出量 = 汇点流入量
  • 最大流：在一个 st 网中找出一个流，使该流的流值最大，且知道达到该流值的各个边值
  • st 流：一个 st 网中的流
  • 合并两个顶点集后仍保持流平衡
  • 循环流：
    • 可以用一条从 s 到 t 的边对任何流网络进行扩展，其中流和容量等于网的值，且对任何扩展过的网络中的结点集，其流入量等于流出量
    • 根据流分解定理，可与环集合（每个环一个流值）互相转换
    • 流分解定理：任何循环流可表示为至多有 E 个有向环的集合上的流
      • 任何 st 网中都有一个最大流，满足非零流值所导出的子图是一个环
      • 任何 st 网中都有一个最大流，可表示为从 s 到 t 的至多 E 个有向路径集合上的流
• 增大路径最大流算法：
  • 增大路径法（Ford-Fulkerson 法）：
    • 描述：从任何一个零流开始，沿着从源点到汇点的任何一条路径上的未满前向边或空的后向边增大此流，继续这个过程直到网络中不存在这样的路径
    • 增加流量：
      • 增加前向边的流：前向边未用流量最小值
      • 减少后向边的流：后向边流的限制
    • 前向边：随着流行进（遍历从源顶点到目的顶点的边）
    • 后向边：沿着流逆行（遍历从目的顶点到源顶点的边）
    • 运行时间：
      • 找出一个最大流所需的增大路径数
      • 找出每个增大路径所需的时间
    • 所需增大路径数目至多为 VM，M 为网络中最大边容量
    • 找出最大流：O(VEM)
    • 稀疏网络：O(V^2M)
    • 图搜索策略：边缘集数据结构，找增大路径的方法
      • 最短增大路径：根据路径上边数
        • 增大路径数目：至多为 VE/2
        • 稀疏网：O(V^3)
        • 队列
      • 最大容量增大路径：沿着使流增大最大量的路径增大
        • 增大路径数目：至多为 2ElgM
        • 稀疏网：O(V^2lgMlgV)
        • 优先队列
      • 栈
      • 随机队列
  • st 割：将顶点 s 放在一个集合，顶点 t 放在另一个集合的割
  • 割集：交叉边的集合（连接这两个集合的边的集合）
  • st 割的容量：该割的所有 st 边的容量之和
  • 穿越 st 割的流：割中 st 边流之和减去割中 ts 边流之和
  • 最小割：给定一个 st 网，找出一个使割的容量达到最小的 st 割
  • 对于任何 st 流，流值等于穿越每个 st 割的流
  • st 流的值都不大于任何 st 割的容量
  • 最大流-最小割定理：网中所有 st 流最大值等于所有 st 割最小值
  • 残量网络：顶点和原网相同。对应于原网中的一条边，有一条或两条边
    • 对于原网中每个边 u-v，设 f 为流值，c 为容量，以下容量为权值：
      • 边空（f=0）：有一条容量为 c 的边 u-v（方向不变）
      • 边满（f=c）：有一条容量为 c 的边 v-u（方向相反）
      • 边不空不满，则有两条边：
        • 正向边容量为 c-f（u-v）
        • 逆向边容量为 f（v-u）
• 预流-推进最大流算法：
  • 描述：沿着顶点的出边逐渐移动流，使流入量多于流出量，直到达到一个可行流（不再存在活动顶点）
  • 可行流：满足平衡条件的流
  • 预流：一个流网络中正边流的集合，满足：
    • 边上流值不大于边上容量
    • 对于每个内部结点流入量不小于流出量
  • 活动顶点：流入量大于流出量的内部结点（约定源点、汇点不是活动顶点）
  • 顶点盈残量：活动顶点流入量减去流出量
  • 改变活动顶点的集合：把活动顶点放入广义队列中，取出一个，沿着一个发出边推进盈残量。如果容量不足，则沿着进入边倒推盈残量；如果推进使这个顶点不平衡，则变成不活动顶点，可能也会激活别的顶点
  • 高度函数：
    • 在一个流网络中给定流的高度函数是一个非负顶点权值集合 h(0)…h(V-1)，且满足对于汇点 t 有 h(t) = 0，对于流的残量网络中每条边 u-v，有 h(u) <= h(v) + 1
    • 合格边：残量网络中满足 h(u) = h(v) + 1 的一条边 u-v
    • 没有合格边：h(0) = h(1) = … = h(V-1) = 0
    • 设 h(s) = 1，则从源点出发，且有流的任何边都对应着残量网络中的一条合格边
    • 为每个顶点赋以到汇点的最短路径距离：
      • 即以 t 为根的逆网的 BFS 树中到根结点的距离
      • 定义一个高度函数
      • 步骤：
        1. 到 t 的高度必定为 0
        2. 在残量网络中，高度为 1 的顶点被 t 的顶点直接访问
        3. 高度为 2 的顶点被高度为 1 的顶点直接指向
        4. 以此类推
    • 对于任何流和其所关联的高度函数，一个顶点的高度不大于残量网络中从该顶点到汇点的最短路径的长度
    • 含义：当一个活动顶点的高度：
      • 小于源点高度时：结点向汇点推进流
      • 大于源点高度时：结点超出量可被倒推入源点
    • 顶点高度大于 V：在残量网络中不存在从该顶点到汇点的路径
  • 基于边的预流-推进算法：
    • 有任一高度函数，连接到源点的边充满至容量，其它边赋 0 流
    • 步骤：
      1. 选择一个活动顶点，向离开这个顶点的合格边（依靠高度函数识别）（如果有合格边存在）推进流
      2. 如果不存在这样的边，则增加顶点的高度
      3. 直至没有活动顶点存在
    • 保持了高度函数的有效性：O(V^2E)
  • 预流-推进算法性质：
    • 在流网络中执行时，在流网络的残量网络中存在每个活动顶点到源点的一条有向路径，不存在从源点到汇点的有向路径
    • 执行中时，顶点高度总是小于 2V
    • 可计算一个最大流
  • 基于顶点的预流-推进算法：
    • 步骤：
      1. 选择一个活动顶点，向离开顶点的合格边增加流（如果可能则充满）
      2. 继续直到顶点变成不活动的或者不存在合格边
      3. 不存在合格边时，增加顶点的高度
    • 一旦我们选择一个顶点，就尽可能推进它的所有流，如果到了仍有盈余流的顶点但无合格边，就增加顶点的高度
    • FIFO 队列实现：最坏情况下 V^2E
  • 最高顶点预流-推进最大流算法：返回最高活动顶点的优先队列
  • 3 种选择：
    • 基于边与基于顶点的通用算法
    • 广义队列实现
    • 初始高度赋值
• 最大流归约：
  • 可归约为最大流的问题：
    • 一般网中的最大流
    • 顶点容量约束
    • 无环网最大流
    • 无向网最大流
    • 可行流
    • 最大基数二分匹配（二分匹配）：二分图中找最大基数匹配：O(VE)
  • Menger 定理：在有向图中删除某条边使两个顶点不连通的最少边数等于这两个顶点之间边不相交的路径的最大数目
  • 连通度：
    • 边连通度：把图分割成两部分所需删除的最少边数（边集）
    • 顶点连通度：把图分割成两部分所需删除的最少顶点数（顶点集）
  • 无向图边连通度：
    • O(E^2)
    • 最大割集合边数 = 最小流值 = 边连通度
    • 改进：VE
• 最小成本流：
  • 最小成本流模型：允许边上有整数成本，并以自然地方式使用边的成本来定义流成本，然后求出具有最小成本的最大流
  • 边上流成本：边上流和成本的乘积
  • 流成本：一个流的成本为该流中边流成本之和
  • 最小成本最大流：在有边成本的流网络中找出一个最大流使得不存在有更小成本的其它最大流
  • 最小成本可行流：配送网：在有边成本的流网络中对顶点赋予权值，正权值为供应，负权值为需求，且所有顶点权值（等价的）之和为 0.找出有最小成本的一个可行流（平衡）
  • 残量网络扩展：对于每条边 u-v，设 f 为流值，c 为容量，x 为成本
    • f 为正：有一条容量 f、成本 -x 的边
    • f 为负：有一条容量 c-f、成本 x 的边
    • …
    • 区别：表示后向边的边有负成本
  • 性质：残量网络中不含负成本的环：最小成本最大流
    • 消环算法：
      • 描述：找一个最大流，在残量网中沿着任何负成本的环来增大流，继续这个过程，直到不存在负成本的环
      • 虚拟流初始化（去掉初始最大流的计算）：添加一条从源点到汇点的虚拟边，并赋予最大成本（大于任何源点-汇点路径上的成本）：VC+1；最大流：大于源点流出量
      • 所需的增大环的数目少于 ECM
      • 稀疏图：O(V^3CM)
• 网络单纯形算法：
  • 描述：维护一个树形数据结构，对成本进行重新加权以使负环可被快速识别
  • 对于任意流、每个网络边 u-v 可有 3 种状态：
    • 空：流只能从 u 推入 v：u-v 在残量网中，v-u 不在
    • 满：流只能从 v 推入 u：v-u 在残量网中，u-v 不在
    • 部分（部分边）（不空不满）：流可双向推入：u-v、v-u 都在残量网中
  • 给定一个不含部分边环的最大流，此最大流的一个可行生成树是网络的一棵生成树，包含了所有流的部分边
  • 网络单纯形算法：
    • 第一步：构造一棵生成树：
      • 方法：
        • 计算一个最大流，通过沿着每个环增大从而使其边为空或为满来破坏部分边的环，然后向余下的部分边中添加满边或空边，从而构建一棵生成树
        • 从源点到汇点的一条虚拟边的最大流开始，此边为唯一可能的部分边，可使用任何图搜索方法来构建该流的一棵生成树
    • 基本原理：有一个顶点权值的集合，这些权值可以很快地识别出一些边，这些边被添加到树中时，会在残量网中创建负环
      • 顶点权值：势
      • \phi (v)：关联顶点 v 的势
    • 设 c(u, v) 为流的残量网中 u-v 的成本，对于任何势函数 \phi，该残量网中的边 u-v 关于 \phi 的降低的成本用 c*(u, v) 表示，值为 c*(u, v) = v(u, v) - (\phi (u) - \phi (v))：每条边上降低的成本为该边实际成本减去该边顶点势差
    • 使用可行生成树来定义顶点的势，使得关于这些势的降低的边成本直接给出关于负成本环的信息：通过执行算法和设置顶点势的值（使得所有树边可降低的成本为 0）来维护一棵可行生成树
    • 当所有树边可降低的成本为 0 时，称顶点势的集合关于这棵树是有效的：对于任意给定生成树，所有有效的顶点势隐含着每条网络边有相同的降低成本
    • 合格边：
      • 非树边：如果在残量网络中，它与树边创建的环是一个负成本的环
      • 边：
        • 带有可降低成本为正的一条满边
        • 带有负可降低成本的一条空边
      • 有合格边则有负成本的环
      • 无合格边则为最小成本流
      • 最小成本流：树边的降低成本均为 0，满的非树边均为非负的，空的非树边均为非正的
    • 定义：构建一棵可行生成树并维持顶点的势，使其满足所有树顶点的降低成本为 0。向树中添加一条合格边，并沿着用该边与树边形成的环来增大流，从该树中删除满边或空边，继续这一过程直到不存在合格边
    • 可行生成树：顶点的势：降低的成本：合格边：负成本环：减小流成本：树结构的改变：顶点势的改变
    • 3 种涉及树的计算任务：
      • 计算顶点的势：
        • 步骤：
          1. 设根的势为 0， 从任意顶点开始，递归地计算其祖先的势，沿着父链接直到树根
          2. 然后选择另一个顶点，并使用父链接递归计算其祖先的势
          3. 到达一个势已知的祖先顶点时，递归终止且在跳出递归的过程中沿着路径向下行进，通过相应的父结点来计算每个结点的势，继续这一过程，直到计算了所有结点的势
        • 与 V 呈线性
      • 沿着该环增大（并识别其上的空边或满边）：
        • 最小公共祖先（LCA）：两个结点的最小子树的根
        • 添加一条连接两个结点的边而形成了环，这个环由新边和这两个结点到其 LCA 的两条路径上的边组成
        • 步骤：
          1. 通过这两个结点到其 LCA 的任一路径，沿着环增大。示例：为了沿着通过添加新边 u-v 而形成的环增大，可以找到 u 和 v 的 LCA（设为 t），并从 u 到 v，从 v 沿着到 t 的路径及从 u 沿着到 t 的路径推入流，但在相反方向每条边都推入流
          2. 计算推入的流量，用同样的方法遍历环上的边来确定被推入的最大量
        • 与环结点数成正比
      • 在形成的环上插入一条新边和删除一条边（用 u-v 与树边所创建的环中另一条边来代替边 u-v）：
        • 需删除的边在 u 到 LCA 路径上或 v 到 LCA 路径上
        • 将 u-v 之间的链接反向并删除边
        • 如果在增大环中存在多于一条的满边或空边：总是从树中删除与合格边两个顶点 LCA 最近的边
• 最小成本流归约：
  • 最小成本流更具有一般性：任何最小成本最大流都是最大流问题的一个解
  • 最小成本流消环算法给出了最大流问题的一种通用增大路径算法
  • 在最小成本流问题中，可将负成本网转换为非负成本的网
  • 单纯形方法：网络单纯形方法
  • LP 问题：最小成本流问题
  • 归约：
    • 无负环单源点最小路径问题
    • 运输问题等价于最小成本流
    • 分配问题
    • 邮差问题
• 展望：
  • 最大匹配
  • 多商品流
  • 凸包和非线性成本
  • 调度问题