Kyle's Notebook

最大流问题

Word count: 2.7kReading time: 11 min
2021/07/09

最大流问题

还是有权图,这次来思考最大流问题。

网络流(Network Flow) 是图算法领域中很重要的一种模型。其网络表示为有向有权图,常用于表示水管、交通、网络等。

对于一个表示网络流模型的有向图包含以下特征:

  • 源点(Source):模型中只有一个,入度为 0 的点。

  • 汇点(Sink):模型中只有一个,出度为 0 的点。

  • 容量(Capacity):模型中的边上容纳的流不能超过其容量,即边上的非负权值。

  • 流量(Flow):模型中每有一条流(路径)经过一条边,则该边上的流量 +1。

  • 源点的流出量等于汇点的流入量,对于图中的其他每个顶点,流入量等于流出量。

Max Flow

在此基础上要考虑网络流模型中可容纳的最大流量,即为 最大流问题(Max Flow)

先给出有权图的 Java 实现(省略细节),有权边 WeightedEdge

1
2
3
4
5
6
7
8
9
10
11
12
13
public class WeightedEdge implements Comparable<WeightedEdge> {

// 起点,终点,权值
private final int v, w, weight;

public WeightedEdge(int v, int w, int weight) {
this.v = v;
this.w = w;
this.weight = weight;
}

// ...
}

有权图 WeightedGraph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class WeightedGraph {

// 顶点数,边数
private int V, E;

/**
* 邻接表:使用红黑树描述
* [
* 0: {1: 3, 2: 2, 3: -2},
* 1: (2: 2, 3: 2, 4: 1)
* ]
*/
private TreeMap<Integer, Integer>[] adj;

// 获取权值
public int getWeight(int v, int w) {
if (hasEdge(v, w)) {
return adj[v].get(w);
}
throw new IllegalArgumentException(String.format("No edge %d-%d", v, w));
}

// 边是否存在
public boolean hasEdge(int v, int w) {
return adj[v].containsKey(w);
}

// ...
}

Ford-Fulkerson 思想

要解决最大流问题(求出从源点发出、到汇点接收的流量),首先要理解 Ford-Fulkerson 思想

重要的几点:

  • 选优思路是填满容量最小的边,但如果只关注边的容量,无法达到全局最优(先把源点填满,但中间有边未饱和)。

  • 思考 反向边:可以对一条已经存在流量的边,反向抵消流量,此时看作一条反向边。比如下图中容量为 5 的边:

1
2
3
 [A]
2↑ ↓3
[B]
  • 残量图(Residual Graph):描述图中的边剩余可经过的流量。假设在原图中边 v-w 的容量为 c,流量为 f,则残量图中 v-w 边的权值为 c-fw-v 的权值为 f。

  • 增广路径(Augmenting Path):在残量图中找到从源点 s 到汇点 ``、所有的权值都大于 0 的路径,其流量为路径中边的最小权值。

Ford-Fulkerson 思想可理解为在原图出发创建残量图,在残量图中不断寻找增广路径,每找到一条增广路径则图中流量增加,直到无法再找到增广路径为止,即求得最大流(上图为原图,下图为残量图与增广路径)。

残量图与增广路径

时间复杂度:O(maxflow * E)

Edmonds-Karp 算法

基于 Ford-Fulkerson 思想,目的是寻找增广路径,其步骤是:

  • 创建残量图:在初始时原图中每条边的流量都为 0,因此对于残量图,所有正向边的流量都等于原图对应的容量,反向边流量都为 0。

  • 使用广度优先遍历(BFS)在残量图中寻找从源点到汇点的增广路径(权值为 0 则不能通过)。

  • 每找到一条增广路径,可计算出其流量等于最小权值边的权值 f,因此把原图中对应路径上的边流量 +f、把残量图中对应的边权值更新为 c-f,反向边权值更新为 f

  • 重复执行第二步继续寻找增广路径、更新残量图权值和原图流量。

增广路径

如何在残量图上寻找增广路径?如上所述采用广度优先遍历即可。

采用一个 int[] prev 数组记录当前节点的前一个节点,初始化为 -1 可表示节点未被访问过,>= 0 表示已经访问过且存储上一个节点编号(初始化为 -1,表示未更新)。

1
2
3
int[] prev = new int[V];
Arrays.fill(prev, -1);
prev[s] = s;

在 BFS 循环过程中,取出的节点 cur 首先判断是否为汇点,是则退出循环。否则遍历其邻接节点 next。如果 next 未被访问过,且 curnext 在残量图上的边权值大于 0,则添加到路径数组 prev 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 广度优先遍历。
Queue<Integer> q = new LinkedList<>();
q.add(s);
while(!q.isEmpty()){
int cur = q.remove();
// 遇到汇点,退出循环。
if (cur == t) {
break;
}

// 遍历邻接节点,如邻接节点未访问过,且在残量图上、与邻接节点的边权值大于 0,则添加到路径。
for (int next: rG.adj(cur)) {
if(prev[next] == -1 && rG.getWeight(cur, next) > 0) {
prev[next] = cur;
q.add(next);
}
}
}

在退出循环时,利用 prev 数组还原增广路径并返回(必须到达汇点 t)。

1
2
3
4
5
6
7
8
9
10
11
12
// 还原增广路径并返回(必须到达汇点)。
LinkedList<Integer> res = new LinkedList<>();
if (prev[t] == -1) {
return res;
}
int cur = t;
while(cur != s){
res.addFirst(cur);
cur = prev[cur];
}
// 最后把源点加上。
res.addFirst(s);

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class WeightedGraph {
// ...
private List<Integer> getAugmentingPath(int s, int t, WeightedGraph rG) {

// 记录顶点是否被遍历过、当前顶点的前一个顶点(初始化为 -1,>= 0 表示已经遍历过,且存储上一个节点)。
int[] prev = new int[V];
Arrays.fill(prev, -1);
prev[s] = s;

// 广度优先遍历。
Queue<Integer> q = new LinkedList<>();
q.add(s);
while(!q.isEmpty()){
int cur = q.remove();
// 遇到汇点,退出循环。
if (cur == t) {
break;
}

// 遍历邻接节点。
for (int next: rG.adj(cur)) {
// 邻接节点未访问过,且在残量图上、与邻接节点的边权值大于 0,则添加到路径。
if(prev[next] == -1 && rG.getWeight(cur, next) > 0) {
prev[next] = cur;
q.add(next);
}
}
}

// 还原增广路径并返回(必须到达汇点)。
LinkedList<Integer> res = new LinkedList<>();
if (prev[t] == -1) {
return res;
}
int cur = t;
while(cur != s){
res.addFirst(cur);
cur = prev[cur];
}
res.addFirst(s);
return res;
}
}

求解最大流

有了求增广路径的方法,求解最大流就很容易实现了,简单讲解一下实现细节。

创建残量图:残量图与原图有相同的结构,其中原图的容量即残量图的权值,且原图的反向边在残量图中表示为权值 0(初始状态时由于正向边没有流量,反向边也没有流量抵消)。

1
2
3
4
5
6
7
8
WeightedGraph rG = new WeightedGraph(V, true);
for (int v = 0; v < V; v++) {
for (int w : adj(v)) {
// 原图的容量 => 残量图的权值,反向为 0(初始时正向边没有流量,反向边也没有流量抵消)。
rG.addEdge(v, w, getWeight(v, w));
rG.addEdge(w, v, 0);
}
}

创建完成后,在残量图上循环执行最大流 maxFlow 的统计:

在残量图中循环寻找增广路径,每找到一条增广路径则访问其上的所有边,统计边的最小权值(即流量) f 并累加到最大流上。

1
2
3
4
5
6
int f = Integer.MAX_VALUE;
for (int i = 1; i < augPath.size(); i++) {
int v = augPath.get(i - 1), w = augPath.get(i);
f = Math.min(f, rG.getWeight(v, w));
}
maxFlow += f;

根据增广路径更新残量图的流量:遍历增广路径的每条边,考虑其两个顶点 vw,正向减去 f,反向加上 f(边 v-w 的流量就是残量图的反向边的权值,也即可抵消的流量)。

1
2
3
4
5
6
for (int i = 1; i < augPath.size(); i++) {
int v = augPath.get(i - 1), w = augPath.get(i);
// 正向减去增广路径的最小权值,反向加上增广路径的最小权值。
rG.setWeight(v, w, rG.getWeight(v, w) - f);
rG.setWeight(w, v, rG.getWeight(w, v) + f);
}

循环以上步骤直到找不到增广路径,此时 maxFlow 的值即为网络流模型的最大流。完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class WeightedGraph {
// ...
public int maxFlowEdmondsKarp(int s, int t) {
// 省略参数校验,以下代码默认在有向有权图、图节点数 > 2 且源点不等于汇点时有效。

int maxFlow = 0;

// 创建残量图。
WeightedGraph rG = new WeightedGraph(V, true);
for (int v = 0; v < V; v++) {
for (int w : adj(v)) {
// 原图的容量 => 残量图的权值,反向为 0(初始时正向边没有流量,反向边也没有流量抵消)。
rG.addEdge(v, w, getWeight(v, w));
rG.addEdge(w, v, 0);
}
}

// 在残量图中寻找增广路径。
while (true) {
List<Integer> augPath = getAugmentingPath(s, t, rG);

// 找不到增广路径,已求出最大流,返回。
if (augPath.size() == 0) {
return maxFlow;
}
// 访问增广路径上所有的边,计算边最小权值,累计到最大流上。
int f = Integer.MAX_VALUE;
for (int i = 1; i < augPath.size(); i++) {
int v = augPath.get(i - 1), w = augPath.get(i);
f = Math.min(f, rG.getWeight(v, w));
}
maxFlow += f;

// 根据增广路径更新 rG 的流量。
for (int i = 1; i < augPath.size(); i++) {
int v = augPath.get(i - 1), w = augPath.get(i);
// 正向减去增广路径的最小权值,反向加上增广路径的最小权值。
rG.setWeight(v, w, rG.getWeight(v, w) - f);
rG.setWeight(w, v, rG.getWeight(w, v) + f);
}
}
// 边 v-w 的流量,即残量图的反向边的权值(可抵消的流量)。
// int flow = rg.getWeight(w, v);
}
}

时间复杂度:O(V*E^2)

总结

最大流算法应用广泛,其中最典型的一类就是匹配问题(Matching)。其本质是在图上选边,边的集合中不允许一个顶点出现两次。

因此匹配问题是基于二分图的建模,其中包括最大匹配(匹配数量最多的方案)、完全匹配(所有的顶点都纳入匹配方案中,必然是最大匹配)。

利用最大流思想解决匹配问题:

  • 建立网络流模型,引入虚拟的源点和汇点、分别与二分图两边的顶点相连。

  • 将原图的无向边改为有向边,所有的边容量设为 1。

  • 再参照最大流算法即可求得最大匹配数(即为最大流的值)。

本文只是介绍了求解最大流问题最基础的 Edmonds-Karp 算法,实际上这类问题还有很多复杂的优化,比如 Dinic 算法、MPM 算法。

另外普林斯顿大学的算法课程上也有一道经典的棒球比赛问题(COS 226 Programming Assignment. Baseball Elimination),感兴趣的朋友可以自行查阅相关资料、思考一下如何运用网络流模型解决实际问题。

参考

CATALOG
  1. 1. 最大流问题
    1. 1.1. Ford-Fulkerson 思想
    2. 1.2. Edmonds-Karp 算法
      1. 1.2.1. 增广路径
      2. 1.2.2. 求解最大流
    3. 1.3. 总结
    4. 1.4. 参考