图论模型与算法

图的表示方法

本书中的图通过空间复杂度 $O(|V| + 3 * |E|)$ 表示（无向图的边需要通过两条有向边表示）：

• first：长度为 $|V|$ 的数组，每个元素 x 表示从 x 出发的第一条边；
• u、v：长度为 $|E|$ 的数组，分别存储着边关联的两个节点；
• next：长度为 $|E|$ 的数组，边的邻接链表的下一条边；

树

无根树转化为有根树

转化代码：

1
2
3
4
5
6
7
8
9

void dfs(int u, int fa)
{
  int d = G[u].size();
  for (int i = 0; i < d; i++)
  {
    int v = G[u][i];
    if (v != fa) dfs(v, p[v] = u);
  }
}

表达式树

二叉树是表达式处理的常用工具，其中每个非叶子节点都表示一个运算符，它的左子树是这个运算符的第一个运算数，右子树则是这个运算符的第二个运算数。

如何通过一个字符串建立表达式树呢，方法有很多种（详见《编译原理》）。

最小生成树

在无向图中，连通且不含圈的图称为树。

如果给定无向图 G=(V,E)，如果存在一个 E 的子集连接了 V 中的所有点，那我们称这个子集为 G 的生成树，而权值最小的生成树则被称为最小生成树（Minimal Spanning Tree, MST）。

求一个 MST 的方法有很多种，最常见的有两种：Kruskal 算法和 Prim 算法，https://zhihu.com/question/27566032/answer/287968877

并查集

在上面的最小生成树问题中，有一个常见的图论问题要处理：

• 如何判断图中的两个点是否属于同一个“连通分量”（即一个连通图的所有点的集合）；
• 通过添加一个边的方法将两个“连通分量”合并。

上面这两个诉求有这样的特点：

• 我们只关心连通这一个信息，不关心具体的连通方式，类似于一个集合；

这个问题可以用一个树状结构“并查集”表示，并查集由多个集合构成，每个集合通过一颗树状的结构表示，两个节点如果属于同一个“连通分量”，那么它们一定属于同一棵树，这棵树的根节点被称为这个集合的“代表元”（representative）。

实现一个并查集核心在与 find 方法 ，即如何找到一个给定节点所在的树的代表元：

1
2
3

int find(int x) {
  return p[x] == x ? x : p[x] = find(p[x]);
}

最短路问题

Dijkstra 算法

之前动态规划的章节中有提到 DAG 中的动态规划可以用于解决最短路问题。但是如果图中有环，那么之前的方法就不适用了。

Dijkstra 算法可以用于计算正权图上的单源最短路问题（SSSP, Single-Source Shortest Paths）。用 w[i][j] 表示两个边之间的权值（INF 表示不连接），d[i] 表示源节点到节点 i 的距离，那么 Dijkstra 算法是实现如下：

1
2
3
4
5
6
7
8
9

memset(v, 0, sizeof(v));
for (int i = 0; i < n; i++) d[i] = i == 0 ? 0 : INF;
for (int i = 0; i < n; i++)
{
  int x, m = INF;
  for (int y = 0; y < n; y++) if (!v[y] && d[y] <= m) m = d[x=y];
  v[x] = 1;
  for (int y = 0; y < n; y++) d[y] <?= d[x] + w[x][y];
}

简单地来说，Dijkstra 算法分为以下两步：

1. 在所以未访问的节点中，找出距离源节点最近的节点 x；
2. 给 x 做标记，并且更新所有与 x 响铃的点到源节点的距离；

我们通常把这个算法的第二步称为松弛操作（relexation）。

优化 Dijkstra 算法

邻接表（Adjacency List）：一种稀疏图（Sparse Graph）的表示方式。在这种表示法中，每个结点 i 都有维护一个链表，里面保存着从 i 出发的所有边。

以下是一个从读入开始的例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int n, m;
int first[MAXN];
int u[MAXM], v[MAXM], w[MAXM], next[MAXM];
void read_graph()
{
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) first[i] = -1;
  for (int e = 0; e < m; e++) 
  {
    scanf("%d%d%d", &u[e], &v[e], &[e]);
    next[e] = first[u[e]];
    first[u[e]] = e;
  }
}

其中：

• u/v/w 都是原始输入，分别为编号为 e 的边连接的两个节点，以及这个边的权值；
• first 表示编号为 i 的节点的第一个边，用 next 连接所有的边；

使用邻接表可以优化 Dijkstra 算法的第二步，从 O(n) 优化到 O(m)。对于算法的第一步，即“找出未标号节点中的最小 d 值”，可以使用优先级队列进行优化。

使用优先级队列的代码实现如下：

1
2
3
4
5
6

struct cmp {
  bool operator() (const int a, const int b) {
    return a % 10 > b % 10;
  }
}
priority_queue<int, vector<int>, cmp> q;

使用优先级队列可以把第一步的复杂度从 O(n) 降低到 O(logn)。

Bellman-Ford 算法

与 Dijkstra 算法类似，Bellman-Ford 算法主要分为以下两步：

1. 遍历所有节点，对每个结点执行松弛操作；
2. 更新当前遍历节点的所有相邻节点，对他们也执行松弛操作。

这个算法的朴素实现是 O(mn)，具体在实现时可以使用 FIFO 进行优化：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

queue<int> q;
bool inq[MAXN];
for (int i = 0; i < n; i++) d[i] = i == 0 ? 0 : INF;
memset(inq, 0, sizeof(inq));
q.push(0);
while(!q.empty()) {
  int x = q.front(); q.pop();
  inq[x] = false;
  for (int e = first[x]; e != -1; e = next[e]) if (d[v[e]] > d[x] + w[e]) {
    d[v[e]] = d[x] + w[e];
    if (!inq[v[e]]) {
      inq[v[e]] = true;
      q.push(v[e]);
    }
  }
}

Floyd 算法

如果你仅仅需要计算两个点之间的最短路，不必调用 n 次 Dijkstra（边权均为正）或者 Belman-Ford（有负权）。只需要使用下面的 Floyd-Warshall 算法：

1
2
3
4

for (int k = 0; k < n; k++)
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      d[i][j] <?= d[i][k] + d[k][j]

网络流初步

增广路定理

对于一个网络拓扑图 G=(V, E)，对于每条边 $$(u, v) \in E$$，有一个运送物品的上限称为容量 c(u,v)，它在一个特定的问题下实际运送的物品数量称为流量 f(u, v)。

最大流问题：求一个方案，把最多的物品从 s 运送到 t（其中 $$s, t \in V$$）

问题中通过 f、c 建模描述的最大流问题满足这样的一些性质：

1. 容量限制：$$f(u, v) \le c(u, v)$$
2. 斜对称性：$$f(u, v) = -f(v, u)$$
3. 流量平衡：对于除了 s、t 之外的任意节点 u，$$\displaystyle \sum_{(u, v) \in E} f(u, v) = 0$$

残量网络（residual network）：

• 对于 E 中的每一条边 (u,v) 都有 f、c 两个属性值，对图中的每一条边进行计算，将 (u, v) 这样一个有向边分解成两个有向边：u 到 v 且权值为 f；v 到 u 且权值为 c-f；
• 通过这样的方式构造出来的一张新图称为残量网络

增广（augmenting）：

• 在残量网络中找出任意一条从 s 到 t 的有向路径，找出道路中所有残量的最小值 d，把对应所有边上的流量增加 d。
• 上面描述的这个过程称为增广。

增广路定理：

• 当且仅当残量网络中不存在 s-t 有向路径时，此时状态对应的流是 s 到 t 的最大流。

根据增广路定理我们可以使用 BFS 遍历所有路径，这被称为 Edonds-Karp 算法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

queue<int> q;
memset(flow, 0, sizeof(flow));
f = 0;
while (true) {	// 循环出口是，找不到从 s 到 t 的路径
  memset(a, 0, sizeof(a));
  a[s] = INF;
  q.push(s);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v = 1; v <= n; v++) if (!a[v] && cap[u][v] > flow[u][v]) {
      p[v] = u; q.push(v);
      a[v] = a[u] <? cap[u][v] - flow[u][v];
    }
  }
  if (a[t] === 0) break;
  for (int u = t; u != s; u = p[u]) {
    flow[p[u]][u] += a[t];
    flow[u][p[u]] -= a[t];
  }
  f += a[t];
}

其中 a[i] 表示在当前路径下，从源节点 s 到 i 的最小残量，那么 a[t] 就是整个链路的最小残量。

最小割最大流定理

割：

• 把图的所有顶点分成 S、T 两个集合，其中 $$s \in S, t \in T$$，把集合 $${e = (u, v)| u \in S, v \in T}$$ 中的所有边删除，就无法从 s 达到 t 了。
• 我们把这样的集合划分方式称为一个 s-t 的割。

一个割的容量可以定义为：$$\displaystyle c(S, T) = \sum_{u \in S, v \in T} c(u, v)$$，求容量最小割的问题即最小割问题。

最小割最大流定理：

• 在增广路算法中，循环结束的条件是找不到一个从 s 到 t 的路径，在最后一个循环周期中，从 s 通过 BFS 到达过的节点可以组成一个集合 S，它与剩下节点的集合 T 就构成一个 s-t 割；

• 通过上面的映射关系从最大流映射到的割，就是最小割；

证明：通过 $$|f| \le c(S, T)$$

最小费用最大流问题

建模时可以用负数表示容量，使用 Bellman-Ford 算法而不是 BFS。

全图最小割

参考：

• https://www.zhihu.com/question/265186138/answer/290726001
• https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm

全局最小割（或“全局割”）即图的所有割中，容量最小的割成为这个图的全局最小割。

随机算法 Karger’s Algorithm：

• 算法描述：对一个图 $$G = (V, E)$$，随机选择图中的一条边 $$e = (v_1, v_2) \in E$$，对这条边链接的两个点 $$v_1, v_2$$ 进行“缩点”，知道图中只剩下两个点，这两个点对应着原图的一个割。随机执行多次之后可以找到概率上的最小割。
• 概率计算：即每次缩点结束后得到的割，是原图的最小割的概率是多少：
  1. 设图的最小割中，两个集合之间的边集为 $$E’$$，那么考虑随机算法的第一步，成功的概率为 $$\displaystyle 1 - \frac{|E’|}{|E|}$$；
  2. 因为边集 $$E’$$ 构成的割是原图最小割，每个节点的度都应该小于他的势，那么一定满足条件 $$\displaystyle \sum_{v \in V}|E’| \le 2|E| \Rightarrow |E| \ge \frac{|V||E’|}{2} $$
  3. 综合以上两个不等式，对第一次成功的概率有不等式：$$\displaystyle p_{first} = 1 - \frac{|E’|}{|E|} \ge 1 - \frac{2 |E’|}{|V| |E’|} = 1 - \frac{2}{|V|}$$
  4. 上面的概率不等式与 $$|E’|$$ 无关的，所以我们可以递归地计算综合概率：$$\displaystyle p_n \ge (1 - \frac{2}{|V|}) p_{n-1} = \prod_{i = 0}^{n-3}\frac{|V| - i - 2}{|V| - i} = \frac{1}{C_{|V|}^2}$$
• 时间复杂度计算：考虑执行 $$T = C_{|V|}^2 \ln{|V|}$$ 次随机的计算：
  1. 可以认为 $$C^{2}{n}$$ 是一个极大的数字，在进行了 T 次计算后失败概率 $$\displaystyle (1 - \frac{1}{C{|V|}^2})^{C_{|V|}^2 \ln{|V|}} \rightarrow (\frac{1}{e})^{\ln{|V|}} = \frac{1}{|V|}$$
  2. 执行 T 次计算的总时间复杂度为：$$O(T |E|) \approx |V|^2 |E| \ln{|V|}$$

迭代算法 Stoer-Wagner Algorithm：

• 算法描述：对于一个图 $$G = (V, E)$$：
  1. 随机初始化一个点集 $$A = { v | v \in V }$$，依次将缩点成本（$\displaystyle v \in V/A \rightarrow \sum_{u \in A, uv \in E} w(uv)$）最大的点加入点集；
  2. 直到加入倒数第二个点 $v_{penult}$，剩下最后一个点 $$v_{last}$$，那么 $v_{penult}-v_{last}$ 的最小割即 ${v | v \in A, v \not= v_{last}}, {v_{last}}$
  3. 重复前面两个步骤 $|V| - 1$ 次，每次可以得到一个最小割，这些最小割中最小的即全局最小割；