温习Algs4 (六):网络流

绝地灬酷狼 2022-04-04 05:46 249阅读 0赞

### 网络流 ###

*  数据模型
 *   *  FlowEdge.java
     *  FlowGraph.java
 *  Max Flow API
 *   *  MaxFlow.java
 *  最大流 Ford-Fulkerson算法
 *   *  FordFulkerson.java

# 数据模型 #

网络流图是在有向图的基础上, 每条边多了两个属性: 流量和最大容量, 因此先定义网络流的边类 FlowEdge:

## FlowEdge.java ##

/****************************************************************************** * Compilation: javac FlowEdge.java * Execution: java FlowEdge * Author: Chenghao Wang ******************************************************************************/
    
    public class FlowEdge { 
        private int from;
        private int to;
        private int flow;
        private int capacity;
    
        FlowEdge() {  }
    
        FlowEdge(int f, int t, int c) { 
            from = f;
            to = t;
            capacity = c;
            flow = 0;
        }
    
        int other(int v) { 
            if (from == v) return to;
            return from;
        }
    
        int available(int frm) { 
            if (from == frm) return capacity - flow;
            return flow;
        }
    
        void addFlow(int frm, int flw) { 
            if (from == frm) flow += flw;
            else flow -= flw;
        }
    }

网络流图的图类和有向图几乎一样, 故不赘述

## FlowGraph.java ##

/****************************************************************************** * Compilation: javac FlowGraph.java * Execution: java FlowGraph * Author: Chenghao Wang ******************************************************************************/
    
    import java.util.Scanner;
    
    public class FlowGraph { 
    
        private int vertexCount;
        private int edgeCount;
        private static Bag<FlowEdge>[] adj;
    
        FlowGraph(int v) { 
            vertexCount = v;
            edgeCount = 0;
            adj = (Bag<FlowEdge>[]) new Bag[v];
            for (int i = 0; i < v; i++) { 
                adj[i] = new Bag<FlowEdge>();
            }
        }
    
        FlowGraph(Scanner scan) { 
            this(scan.nextInt());
            int e = scan.nextInt();
            for (int i = 0; i < e; i++) { 
                int from = scan.nextInt();
                int to = scan.nextInt();
                int capacity = scan.nextInt();
                addEdge(from, to, capacity);
            }
        }
    
        public int V() { 
            return vertexCount;
        }
    
        public int E() { 
            return edgeCount;
        }
    
        public void addEdge(int from, int to, int capacity) { 
            FlowEdge fe = new FlowEdge(from, to, capacity);
            adj[from].add(fe);
            adj[to].add(fe);
            edgeCount++;
        }
    
        public Iterable<FlowEdge> adj(int v) { 
            return adj[v];
        }
    
        public String toString() { 
            StringBuilder sb = new StringBuilder();
            sb.append("<flowgraph>\n");
            for (int i = 0; i < vertexCount; i++) { 
                for (FlowEdge edge : adj[i]) { 
                    int from = edge.from();
                    int to = edge.to();
                    int flow = edge.flow();
                    int capacity = edge.capacity();
                    if (to >= from) { 
                        sb.append(" " + to + " -" + flow + "/" + capacity + "- " + to + "\n");
                    }
                }
            }
            sb.append("</flowgraph>");
            return sb.toString();
        }
    }

# Max Flow API #

先定义一个MaxFlow算法的API, 之后的多个最大流算法都是它的子类

## MaxFlow.java ##

/****************************************************************************** * Compilation: javac MaxFlow.java * Execution: java MaxFlow.java * Author: Chenghao Wang ******************************************************************************/
    
    public abstract class MaxFlow { 
        protected FlowGraph graph;
        protected int source; // 源点
        protected int sink; // 汇点
        protected int maxFlow;
    
        MaxFlow() {  }
        MaxFlow(FlowGraph g, int src, int dst) { 
            graph = g;
            source = src;
            sink = dst;
        }
    
        public int maxFlow() { 
            return maxFlow;
        }
    }

# 最大流 Ford-Fulkerson算法 #

计算最大流的逻辑很简单, 即:

1.  找到一条从源点到汇点的 *增广路径* (即一条还有剩余流量的简单路径)
2.  计算该路径的瓶颈流量, 然后给路径上的各个边都增加该流量
3.  重复1, 2 直到没有增广路径

其中寻找增广路径可以采用 BFS 的方法, 用 pathTo\[\] 数组存储每一节点之前的的 FlowEdge, 这样只要一旦找到汇点,就可以沿着该数组一直遍历到源点, 从而得到瓶颈流量并更新.

## FordFulkerson.java ##

/****************************************************************************** * Compilation: javac FordFulkerson.java * Execution: java FordFulkerson.java * Author: Chenghao Wang ******************************************************************************/
    
    public class FordFulkerson extends MaxFlow { 
    
        private Queue<Integer> queue = new Queue<Integer>();
        private boolean[] mark;
        private FlowEdge[] pathTo;
    
        FordFulkerson() {  }
        FordFulkerson(FlowGraph g, int src, int dst) { 
            super(g, src, dst);
            mark = new boolean[g.V()];
            pathTo = new FlowEdge[g.V()];
            maxFlow = calculate();
        }
    
        private boolean find() { 
            for (int i = 1; i <= graph.V(); i++) mark[i] = false;
            while (!queue.isEmpty()) queue.dequeue();
            queue.enqueue(source);
            mark[source] = true;
            while (!queue.isEmpty()) { 
                int curr = queue.dequeue();
                for (FlowEdge e : graph.adj(curr)) { 
                    int next = e.other(curr);
                    if (mark[next] || (e.available(curr) == 0)) continue;
                    mark[next] = true;
                    pathTo[next] = e;
                    queue.enqueue(next);
                    if (next == sink) return true;
                }
            }
            return false;
        }
    
        private int calculate() { 
            int result = 0;
    
            while (find()) { 
                int bottleneck = Integer.MAX_VALUE;
                int curr = sink;
                FlowEdge edge = pathTo[curr];
    
                while (curr != source) { 
                    int prev = edge.other(curr);
                    bottleneck = Math.min(bottleneck, edge.available(prev));
                    curr = prev;
                    edge = pathTo[curr];
                }
    
                result += bottleneck;
    
                curr = sink;
                edge = pathTo[curr];
                while (curr != source) { 
                    int prev = edge.other(curr);
                    edge.addFlow(prev, bottleneck);
                    curr = prev;
                    edge = pathTo[curr];
                }
            }
            return result;
        }
    }