理解和实现Ford Fulkerson算法有困难

Question

我试图在Java实现Ford Fulkerson算法。到目前为止，我有了一个带节点和边的图。节点包含一个ID字符串和一个边的邻接列表。边包含容量和它通向的节点。

我正在尝试理解维基百科页面上的psudo代码，以及如何实现它（我正在使用Java）。这是我目前所理解的：

>

首先我将图中所有边的流设置为零。（什么是表示流的好方法？直接在我的图的边中作为变量？）

第二步是创建残差图，它是一个网络，其中边具有残差容量：容量-流（“法线图”中相应边的）。然后使用这个残差图找到一条从源到宿的路径，并找到沿着这条路径的最小容量。（这就是事情变得非常棘手的地方，我应该为残差图创建一个全新的图，还是应该以某种方式在原始图中表示它？最好的方法是什么？）

重复步骤2,直到找不到路径为止,但每次找到路径时,您都执行步骤3和4：

>

对于沿路径的每条边，添加步骤2中找到的最小值。

对于路径相反方向的每个边，减去步骤2中找到的最小值。

第3步和第4步让我迷惑不解，因为我觉得在一个方向上做加法和在相反方向上做减法是一样的。这些加减法是在图上做的对吧，不是在残差图上做的？

我真的很感谢你的帮助，我已经想了好几个小时了，但我似乎就是不明白。

Answer 1

这里是Ford-Fulkerson方法的实现，使用深度优先搜索(DFS)，使用邻接列表存储容量。与使用Ford-Fulkerson的邻接矩阵相比，使用邻接列表的棘手之处在于，您需要自己跟踪剩余边。为了简化操作，我创建了一个“Add Edge”方法来处理剩余边缘。不过，使用邻接列表而不是邻接矩阵的好处是，时间复杂度从O(fv²)降低到O(fE)，这可能很重要。

在高层，大多数流算法的工作原理基本相同。他们所做的只是从一个源节点开始，并使用某种技术（在下面的示例中是深度优先搜索），找到一个到接收器（结束节点）的扩展路径。一旦找到了扩展路径，您将沿着路径的每个边的容量减少瓶颈值，并将该值添加到残差图中。你重复这个过程，直到没有更多的增加路径可以找到一个宾果，就是这样！这些都是你需要找到最大流量和最小切割的所有步骤。

代码取自我的算法回购。请随意查看，这里也有这个算法的邻接矩阵版本。

/**
 * An implementation of the Ford-Fulkerson (FF) method with a DFS
 * as a method of finding augmenting paths. FF allows you to find
 * the max flow through a directed graph and the min cut as a byproduct.
 *
 * Time Complexity: O(fE), where f is the max flow and E is the number of edges
 * 
 * @author William Fiset
 **/

import java.util.ArrayList;
import java.util.List;

public class FordFulkersonDfsSolverAdjacencyList {

  public static class Edge {
    public Edge residual;
    public int to, capacity;
    public final int originalCapacity;
    public Edge(int to, int capacity) {
      this.to = to; 
      this.capacity = capacity;
      this.originalCapacity = capacity;
    }
  }

  // Inputs
  private int n, source, sink;

  // Internal
  private int visitedToken = 1;
  private int[] visited;
  private boolean solved;

  // Outputs
  private int maxFlow;
  private boolean[] minCut;
  private List<List<Edge>> graph;

  /**
   * Creates an instance of a flow network solver. Use the {@link #addEdge(int, int, int)}
   * method to add edges to the graph.
   *
   * @param n      - The number of nodes in the graph including source and sink nodes.
   * @param source - The index of the source node, 0 <= source < n
   * @param sink   - The index of the source node, 0 <= sink < n
   */
  public FordFulkersonDfsSolverAdjacencyList(int n, int source, int sink) {
    this.n = n;
    initializeGraph();
    this.source = source;
    this.sink = sink;
  }

  /**
   * Adds a directed edge (and residual edge) to the flow graph.
   *
   * @param from     - The index of the node the directed edge starts at.
   * @param to       - The index of the node the directed edge end at.
   * @param capacity - The capacity of the edge.
   */
  public void addEdge(int from, int to, int capacity) {
    Edge e1 = new Edge(to, capacity);
    Edge e2 = new Edge(from, 0);
    e1.residual = e2;
    e2.residual = e1;
    graph.get(from).add(e1);
    graph.get(to).add(e2);
  }

  /**
   * Returns the graph after the solver has been executed. This allow you to
   * inspect each edge's remaining {@link Edge#capacity} compared to the
   * {@link Edge.originalCapacity} value. This is useful if you want to figure 
   * out which edges were used during the max flow.
   */
  public List<List<Edge>> getGraph() {
    solve();
    return graph;
  }

  // Returns the maximum flow from the source to the sink.
  public int getMaxFlow() {
    solve();
    return maxFlow;
  }

  // Returns the min-cut of this flow network in which the nodes on the "left side"
  // of the cut with the source are marked as true and those on the "right side" 
  // of the cut with the sink are marked as false.
  public boolean[] getMinCut() {
    solve();
    return minCut;
  }

  // Performs the Ford-Fulkerson method applying a depth first search as
  // a means of finding an augmenting path. The input consists of a directed graph
  // with specified capacities on the edges.
  public void solve() {
    if (solved) return;

    maxFlow = 0;
    visited = new int[n];
    minCut = new boolean[n];

    // Find max flow.
    int flow;
    do {
      // Try to find an augmenting path from source to sink
      flow = dfs(source, Integer.MAX_VALUE);
      visitedToken++;
      maxFlow += flow;
    } while(flow != 0);

    // Find min cut.
    for(int i = 0; i < n; i++)
      if (visited[i] == visitedToken-1)
        minCut[i] = true;

    solved = true;
  }

  private int dfs(int node, int flow) {
    // At sink node, return augmented path flow.
    if (node == sink) return flow;

    List<Edge> edges = graph.get(node);
    visited[node] = visitedToken;

    for (Edge edge : edges) {
      if (visited[edge.to] != visitedToken && edge.capacity > 0) {

        // Update flow to be bottleneck 
        if (edge.capacity < flow) flow = edge.capacity;
        int dfsFlow = dfs(edge.to, flow);

        // Update edge capacities
        if (dfsFlow > 0) {
          Edge res = edge.residual;
          edge.capacity -= dfsFlow;
          res.capacity  += dfsFlow;
          return dfsFlow;
        }

      }
    }
    return 0;
  }

  // Construct an empty graph with n nodes including the source and sink nodes.
  private void initializeGraph() {
    graph = new ArrayList<>(n);
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
  }

}

Answer 2

您可能应该首先使用密集图来实现这一点。这样，你就可以假设在每对不同的顶点之间，每个方向都有一条边。你可以把边上的函数表示为vxv矩阵。特别是,容量和流量的声明非常简单：

int[][] cap = new int[numverts][numverts];
int[][] flow = new int[numverts][numverts];

一个有用的技巧是将沿edgevw的k单元的流表示为从v到w的a流和从w到v的-a流。这样，您就不必担心扩展路径的每一个边缘是向前推动了更多的流量还是向后推动了更少的流量。如果您这样做，您可以通过简单的cap[v][w]-flow[v][w]来计算沿vw的剩余容量。

利用这种表示法，在稠密图中寻找增广路径成为广度优先搜索，在稠密图中，当cap[v][w]>flow[v][w]时，正好存在从v到w的边。这是相当直接的实现。

因为您使用的是Java，所以您应该注意它的每个对象开销。您描述的边缘结构不仅包含两个int（或指针）和两个double，还包含诸如GC信息、一个klass指针和一个监视器之类的东西。这是几十个额外的html" target="_blank">字节，很容易使对象的大小增加一倍或三倍。

当您开始使代码使用稀疏图时，静态稀疏图的一个更好的表示形式如下：

int[] from = new int[numverts+1];
int[] to = new int[numedges];

按“from”顶点对边进行排序。from数组的i第条条目是其“from”顶点是i第条顶点或更晚的第一条边的索引。结尾处有一个额外的条目，您应该将其设置为numedges；当你想要在离开给定顶点的所有边上循环时，它就派上用场了。

由于您正在处理流，您也希望存储后向边缘，因此请使用一个

int[] rev = new int[numedges];

存储每个边的反向的边索引。现在，您可以在边沿上表示任意函数，例如cap和flow，如下所示：

int[] cap = new int[numedges];
int[] flow = new int[numedges];

因此，是否将这些属性存储在edge结构中是没有意义的，因为edge结构已经消失了。