网络流与最大流

网络流与最大流

考虑一幅有向带权图

如果图中有一个源点，即入度为 0 的节点，上图的节点 0，有一个汇点，它的出度为 0，上图的节点 3，并且图中所有边的权值都是非负的，那么我们可以说这是一个网络流。

同一般的带权图不同，网络流中边的权值不是指从一个节点到达一个节点的距离是多少，耗费是多少，它指的是从一个节点到达另一个节点能够容忍的最大流量，例如从节点 0 到节点 1 它最多能够容忍 3 的流量。除了流量限制以外，还需要满足平衡限制，即流入某个节点的流量必须等于流出该节点的流量，即节点不允许存储流量，也不能产生流量(除了源点和汇点)。

真实世界中很多的问题可以建模为网络流的模型，例如供水系统，图中的边可以看做是水管，其中的权值表示的是水管能够通过的最大流量；又比如通信系统，每条边看做是一个信道，而权值可以看做是信道容量。

源点不断的发出流量，汇点不断接收流量，因为剩余的节点既不生产流量，也不存储流量，所以从源点发出的流量会全部进入到汇点。现在我们比较关心的是，从源点最多能发出多少流量，最终到达汇点，这就是最大流问题。

有向带权图

在讲解如何获得网络的最大流之前，我们先看看怎么表示网络流模型。其实网络流就是一个有向的带权图，我们只需要根据之前的无向带权图进行改造就可以得到有向带权图，改造的过程可以参考之前的无向无权图到有向无权图的改造，其实就是将

adj[v].put(w, weight);
adj[w].put(v, weight);

修改为了

adj[v].put(w, weight);

以此表明是一个有方向的图。另外为了实现后续的算法，我们为带权图增加了 2 个 API

• setWeight(v, w, weight)
• addEdge(v, w, weight)

另外我们还添加了一个新的构造方法，该方法只接收一个参数，即图中有多少个节点，得到一个没有边的图，在后续通过 addEdge 方法来图添加边。

DirectedWeightedGraph 类如下

import java.io.File;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class DirectedWeightedGraph{
    private int V;
    private int E;
    private HashMap<Integer, Integer>[] adj;

    public DirectedWeightedGraph(String path) {
        File file = new File(path);
        Scanner scanner = null;

        try {
            scanner = new Scanner(file);
            this.V = scanner.nextInt();
            if (V < 0) {
                throw new IllegalArgumentException("V can't be negative");
            }
            adj = new HashMap[V];
            for (int i = 0; i < V; i++) {
                adj[i] = new HashMap<>();
            }

            this.E = scanner.nextInt();
            if (E < 0) {
                throw new IllegalArgumentException("E can't be negative");
            }

            for (int i = 0; i < E; i++) {
                int v = scanner.nextInt();
                int w = scanner.nextInt();
                int weight = scanner.nextInt();

                if (v == w) {
                    throw new IllegalArgumentException("存在自环边");
                }
                if (adj[v].containsKey(w)) {
                    throw new IllegalArgumentException("存在平行边");
                }
			
                // 表示有向
                adj[v].put(w, weight);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }finally {
            scanner.close();
        }
    }

    // 另一构造方法
    public DirectedWeightedGraph(int V) {
        this.V = V;
        this.E = 0;
        this.adj = new HashMap[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new HashMap<>();
        }
    }

    public int V() {
        return this.V;
    }

    public int E() {
        return this.E;
    }

    public int getWeight(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        if (!hasEdge(v, w)) {
            throw new IllegalArgumentException(String.format("%d-%d 不存在", v, w));
        }
        return adj[v].get(w);
    }

    public void setWeight(int v, int w, int weight) {
        validateVertex(v);
        validateVertex(w);
        if (!hasEdge(v, w)) {
            throw new IllegalArgumentException(String.format("%d-%d 不存在", v, w));
        }
        adj[v].put(w, weight);
    }

    public void addEdge(int v, int w, int weight) {
        validateVertex(v);
        validateVertex(w);
        if (v == w) {
            throw new IllegalArgumentException("存在自环边");
        }
        if (adj[v].containsKey(w)) {
            throw new IllegalArgumentException("存在平行边");
        }

        adj[v].put(w, weight);
        E++;
    }

    public boolean hasEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return adj[v].containsKey(w);
    }

    public Iterable<Integer> adj(int v) {
        validateVertex(v);
        return adj[v].keySet();
    }

    public void validateVertex(int v) {
        if (v < 0 && v >= V) {
            throw new IllegalArgumentException("节点超过 [0, V) 的范围");
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("V: %d, E: %d\n", this.V, this.E));
        for (int v = 0; v < this.V; v++) {
            stringBuilder.append(String.format("%d : ", v));
            for (Map.Entry w: adj[v].entrySet()) {
                stringBuilder.append(String.format("(%d: %d) ", w.getKey(), w.getValue()));
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }
}

该类的大部分实现细节与无向的版本相似，如果不熟悉可以查看无向图的相关章节。

Ford-Fulkerson 思想

现在我们开始看一看如何找到图中的最大流，还是以下图为例

我们先从源点随便选择一条路径到达汇点

如上图我们就选择 $0 → 1 → 3$ 这条路径，这条路径能够允许的最大容量为 2，所以这条路径的流量为 2，为了表示已经通过了多少流量，我们以下面形式表示图

左边的数字表示已经通过了多少流量，右边的数字表示允许通过最大容量。接下来我们在选择一条路径

上面我们选择了 $0 → 1 → 2 → 3$ 这条路径，因为 $0 → 1$ 只允许 1 个流量通过了，所以这条路径的流量为 1，我们更新一下图

然后在选择一条路径

这次我们选择了 $0 → 2 → 3$，这条路径的流量为 $2$，更新图如下

接下来我们我们找不到一条路径从源点到汇点了，所以此时我们可以说该网络流的最大流为 $2 + 1 + 2 = 5$。

所以上面的算法就是重复下面两步：

• 随便找一条路径从源点到汇点，找到路径的最小值，就是这条路径的流量
• 更新每条边允许通过的流量

但是真的随便找一条路径就可以吗? 显然不行，例如我们一开始就找到了这么一个路径

这条路径的流量为 3，我们更新图

但是接下来我们发现找不到路径从源点到汇点了，所以我们得出这个网络流的最大路径为 $3$，明显这个答案是不对的，所以我们不能随便选择路径走，因为可能得不到正确的答案。

但是，如果我们允许反向流动呢? 例如还是以上图为例

这次我们选择路径如下

更新后的图为

本来从 $2 → 1$ 是不可达的，但是我们赋予它一个语义，表示将原来通过 $1 → 2$ 的流量引导到别的路径去了，例如本来 $1 → 2$ 有流量为 3，现在我们反向流动 2 个流量，表示将原来这 3 个流量中的 2 个流量引导到别的路径中去了。

赋予这么一个语义的话，那么上面图的所有箭头都可以变为双向的，反向的箭头表示允许被引导到别的路径上，我们给它一个权值，表示能够被允许引导到别的路径上去的流量的最大值，这个值应该是已经通过该路径的流量，例如如果 $1 → 2$ 是用 $3/5$ 表示的话，表示已经有 $3$ 个流量通过 $1 → 2$，那么$2 → 1$ 最多允许 $3$ 个流量被引导。

为了表示方便，不用 $3/5$ 这样的形式来标记边了，而是以剩余允许通过的流量表示边，例如 $3/5$ 表示最大容量为 $5$，已经通过流量为 $3$，所以剩余能够通过的流量为 $2$，我们以 $2$ 来标记这条边，同理我们也以这样的方式标记反向的边，得到下面的这么一个图

黑色表示正向边，红色表示反向边，上面的数值表示能够允许通过的最大流量，可见在最开始反向边是不能允许通过流量的，它们的权值都是 0，这个图我们称之为残差图。

接下下我们就可以使用上面提到的两步了：

• 随便找一条路径从源点到汇点，找到路径的最小值，就是这条路径的流量
• 更新每条边允许通过的流量

这个方法就是 Ford-Fulkerson 思想。

Edmonds-Karp 算法

上面的 Ford-Fulkerson 只是提供了一种思想，得到一个网络流的残差图，然后随便找一条路径从源点到汇点，但是没有说怎么找这条路径，所以它只是一种思想。

接下来我们就介绍 Edmonds-Karp 算法，它就是为 Ford-Fulkerson 提供了一种具体的实现，怎么找一条路径，很简单，那就是从源点进行 BFS 来找到一条路径，当我们通过 BFS 无法达到汇点时，说明网络不能够承受更大的流量了。

所以上面的方法是不是非常的简单，下面就给出具体的实现

import java.util.*;

public class MaxFlow {
    private DirectedWeightedGraph graph;
    private int s;
    private int t;
    private DirectedWeightedGraph rcGraph;
    private int maxFlow = 0;

    public MaxFlow(DirectedWeightedGraph graph, int s, int t) {
        this.graph = graph;

        // 一些校验工作
        if (graph.V() < 2) {
            throw new IllegalArgumentException("网络流中节点个数必须大于1");
        }
        graph.validateVertex(s);
        graph.validateVertex(t);
        this.s = s;
        this.t = t;

        // 根据传入的网络流，构造残差图
        DirectedWeightedGraph rcGraph = new DirectedWeightedGraph(graph.V());
        for (int v = 0; v < graph.V(); v++) {
            for (int w: graph.adj(v)) {
                rcGraph.addEdge(v, w, graph.getWeight(v, w));
                // 一开始反向边能够允许通过的最大流量为 0
                rcGraph.addEdge(w, v, 0);
            }
        }
        this.rcGraph = rcGraph;

        while (true) {
            // 开始从源点做 BFS
            ArrayList<Integer> path =  getAugmentPath();
            // 如果从 BFS 得到的路径为空，说明不能到达汇点了，此时退出循环
            if (path.size() == 0) {
                break;
            }

            // 获得路径的最小值，即这条路径允许通过的最大流量
            int min = Integer.MAX_VALUE;
            for (int i = 1; i < path.size(); i++) {
                int v = path.get(i - 1);
                int w = path.get(i);

                min = Math.min(min, rcGraph.getWeight(v, w));
            }

            maxFlow += min;

            // 更新残差图
            for (int i = 1; i < path.size(); i++) {
                int v = path.get(i - 1);
                int w = path.get(i);

                rcGraph.setWeight(v, w, rcGraph.getWeight(v, w) - min);
                rcGraph.setWeight(w, v, rcGraph.getWeight(w, v) + min);
            }
        }
    }

    // 做 BFS
    private ArrayList<Integer> getAugmentPath() {
        Queue<Integer> queue = new LinkedList<>();
        int[] pre = new int[graph.V()];
        queue.add(s);
        Arrays.fill(pre, -1);
        pre[s] = s;

        while (!queue.isEmpty()) {
            int v = queue.remove();
            for (int w: rcGraph.adj(v)) {
                if (pre[w] == -1 && rcGraph.getWeight(v, w) > 0) {
                    pre[w] = v;
                    queue.add(w);
                }
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        if (pre[t] == -1) {
            return result;
        }

        int cur = t;
        while (cur != s) {
            result.add(cur);
            cur = pre[cur];
        }
        result.add(s);
        Collections.reverse(result);
        return result;
    }

    // 返回网络的最大流
    public int result() {
        return maxFlow;
    }

    // 返回最终 v-w 允许通过的流量
    public int flow(int v, int w) {
        if (!graph.hasEdge(v, w)) {
            throw new IllegalArgumentException("存在这条边");
        }
        graph.validateVertex(v);
        graph.validateVertex(w);

        return rcGraph.getWeight(w, v);
    }
}

棒球比赛

最后我们看一个使用最大流解决实际问题的例子，那就是棒球比赛。

全美每年都会举行一次棒球比赛，每个队都要进行 162 场比赛，最终所胜的场次最多的队伍获胜，如果平局就进行加赛。

但是如果在比赛的过程中，某一队已经没有获得冠军的希望了，那么该队就会被直接淘汰。例如 $A$ 队已经赢了 $10$ 场了，而 $B$ 队只赢了 $1$ 场，并且还有 $8$ 场比赛没有打，此时 $B$ 队如何也不能赢的场次比 $A$ 队多，所以 $B$ 队应该被淘汰。

现在我们拿到了 1996 年 8 月 30 日真实的比赛数据，此时只剩下 5 个队

Teams	Wins	Loss	Left	Against	NY	Bal	Bos	Tor	Det
New York	75	59	28		0	3	8	7	3
Baltimore	71	63	28		3	0	2	7	4
Boston	69	66	27		8	2	0	0	0
Toronto	63	72	27		7	7	0	0	0
Detroit	49	86	27		3	4	0	0	0

Wins 代表赢了多少场，Loss 表示输了多少场，Left 表示剩余多少场没有打，Against 后面的 5 列表示与其他队要打多少场。

当时媒体争议的是最后一个队，即 Detroit 队还有没有获胜的希望。从数据上看，如果 Detroit 剩下的 27 场全赢，那么它的赢的总场次是 $49 + 27 = 76$，比最强的 New York 还多一场，所以它还有赢的机会，但是这样想的话就忽略了一个事实，即使 Detroit 与其他四队的比赛都打赢了，但是这四个队之间还有比赛，也就说说这四个队它们的总胜场是会增加的。

所以现在又变为了这么一个问题，如果前四个队之间比赛，如果最终它们的胜场最多是 76 的话，说明 Detroit 队还有赢的希望，否则 Detroit 队没有赢的可能。现在我们如下建模

这个图分为三部分，第一部分

其中权值表示比赛场次，比如 s → NY-Bal 这条边的权值为 $5$，表示 NY 与 Bal 之间有五场比赛要打，可见这四个队伍总共要打 $5 + 8 + 7 + 2 + 7 = 27$ 场比赛。第二部分

这次的权值表示的是胜场的分配。第三部分

这时其中的权值表示每个队最多赢多少次，例如 NY 队目前 $75$ 分，它最多只能赢一场。如果上述网络流的最大流大于等于比赛的总场次，所以存在一种方案能够分配所有胜场使得所有队的得分最多只有 $76$ 分。

上面网络流我们建模为如下图

11 19
0 1 3
0 2 8
0 3 7
0 4 2
0 5 7
1 6 3
1 7 3
2 6 8
2 8 8
3 6 7
3 9 7
4 7 2
4 8 2
5 7 7
7 9 7
6 10 1
7 10 5
8 10 7
9 10 13

现在我们用之前写的 MaxFlow 类来查看最大流是多少

public class BaseBallSolution {
    public static void main(String[] args) {
        DirectedWeightedGraph baseball = new DirectedWeightedGraph("g17.txt");
        MaxFlow maxflow = new MaxFlow(baseball, 0, 10);
        System.out.println(maxflow.result());
    }
}

结果是

26

说明最大流为 26，小于 27，说明无法分配 27 场比赛使得所有队最多只能赢 76 场，这就意味着 Detroit 没有赢的可能了。