最大流问题

技术算法

Word count: 2.7kReading time: 11 min

 2021/07/09 

最大流问题

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

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

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

源点（Source）：模型中只有一个，入度为 0 的点。
汇点（Sink）：模型中只有一个，出度为 0 的点。
容量（Capacity）：模型中的边上容纳的流不能超过其容量，即边上的非负权值。
流量（Flow）：模型中每有一条流（路径）经过一条边，则该边上的流量 +1。
源点的流出量等于汇点的流入量，对于图中的其他每个顶点，流入量等于流出量。

在此基础上要考虑网络流模型中可容纳的最大流量，即为 最大流问题（Max Flow）。

先给出有权图的 Java 实现（省略细节），有权边 WeightedEdge：

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：

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-f，w-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 未被访问过，且 cur 与 next 在残量图上的边权值大于 0，则添加到路径数组 prev 中。

// 广度优先遍历。
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）。

// 还原增广路径并返回（必须到达汇点）。
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);

完整代码如下：

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（初始状态时由于正向边没有流量，反向边也没有流量抵消）。

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 并累加到最大流上。

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;

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

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 的值即为网络流模型的最大流。完整代码：

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），感兴趣的朋友可以自行查阅相关资料、思考一下如何运用网络流模型解决实际问题。

参考

Next Post

微服务概览与治理
Previous Post

最小生成树问题

CATALOG

1. 最大流问题