残留网络

在介绍最大流算法之前先介绍一下什么是残留网络。残余网络的概念有点类似于集合中的补集概念。

下图是残余网络的例子。上面的网络是原始网络，下面的网络是计算出的残留网络。残留网络的作用就是用来描述这个网络中还剩下多少可以利用的流量。

流量网络

最大流算法比以前介绍的算法都要复杂。网络中的每一条边需要记录容量和当前流量。容量是固定值，是已知条件，而当前流量在计算过程中会一直发生变化。因此，需要建立一个专门的类，用于最大流算法。

public class FlowEdge {
    private int v;
    private int w;
    private double capacity;
    private double flow;
 
    public FlowEdge(int v, int w, double capacity) {
        this.v = v;
        this.w = w;
        this.capacity = capacity;
    }
 
    public int from() {
        return v;
    }
 
    public int to() {
        return w;
    }
 
    public double capactity() {
        return capacity;
    }
 
    public double flow() {
        return flow;
    }
 
    public int other(int v) {
        if (v == this.v) return this.w;
        else return this.v;
    }
 
    // 返回能够增加的最大流量
    public double residualCapacityTo(int v) {
        if (v == this.v) return flow;
        else return capacity - flow;
    }
 
    // 增加这条边的流量
    public void addResidualFlowTo(int v, double d) {
        if (v == this.v) flow -= d;
        else flow += d;
    }
}

与其他的图论算法类似，需要将图中所有的边替换成FlowEdge。于是得到了如下的类。

import java.util.LinkedList;
import java.util.List;

public class FlowNetwork {
    private int V;
    private List<FlowEdge>[] adj;
 
    public FlowNetwork(int V) {
        this.V = V;
        adj = new LinkedList[V];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new LinkedList();
        }
    }
 
    public Iterable<FlowEdge> adj(int v) {
        return adj[v];
    }
 
    public int V() {
        return V;
    }
 
    public void addEdge(FlowEdge e) {
        int v = e.from();
        adj[v].add(e);
    }
 
    @Override
    public String toString() {
        String result = "";
        for (int i = 0; i < V; i++) {
            result += i + ":";
            for(FlowEdge e:adj[i]) {
                result += " " + e.toString();
            }
            result += "\n";
        }
        return result;
    }
}

算法类

按照惯例，需要为最大流算法编写一个专门的类。该类的代码如下：

import java.util.LinkedList;
import java.util.Queue;

public class FordFulkerson {
    private FlowEdge[] edgeTo;
    private double value;
 
    public FordFulkerson(FlowNetwork G, int s, int t) {
        // 一直增加流量直到无法再增加为止
        while (hasAugmentingPath(G, s, t)) {
            // 找出增广路的瓶颈
            double bottle = Double.POSITIVE_INFINITY;
            int v = t;
            while (v != s) {
                bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
                v = edgeTo[v].other(v);
            }
 
            // 增加整条路径的流量
            v = t;
            while (v != s) {
                edgeTo[v].addResidualFlowTo(v, bottle);
                v = edgeTo[v].other(v);
            }
 
            // 最大流增加
            value += bottle;
        }
    }
 
    public double value() {
        return value;
    }
 
    // 判断是否有增广路
    // 有增广路的条件就是存在一条路径，这条路径上所有的边都能增加流量。
    private boolean hasAugmentingPath(FlowNetwork G, int s, int t) {
        edgeTo = new FlowEdge[G.V()]; // 注意，这句话是必须要有的。因为每次增广路径都不一样。
        boolean[] visited = new boolean[G.V()];
 
        // BFS
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(s);
        visited[s] = true; // 注意：这句话不要遗漏
        while (!q.isEmpty()) {
            int v = q.poll();
 
            // 能够通过的条件是流量能够增加
            for (FlowEdge e : G.adj(v)) {
                int w = e.other(v);
                if (e.residualCapacityTo(w) > 0 && !visited[w]) {
                    edgeTo[w] = e;
                    q.add(w);
                    visited[w] = true;
                }
            }
        }
 
        // 有增广路的条件就是S点能够到达T点。
        return visited[t];
    }
 
    public static void main(String[] argv) {
        FlowNetwork g = new FlowNetwork(4);
        int[] data = http://www.mamicode.com/{0, 1, r(), 0, 2, r(), 2, 1, r(), 1, 3, r(), 2, 3, r(), 0, 3, r()};>