1

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

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

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

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

重复第 2 步，直到找不到路径，但每次找到路径时，您都执行第 3 步和第 4 步：

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

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

第 3 步和第 4 步让我感到困惑，因为我觉得在一个方向上添加和在相反方向减去是一回事。这些加减法是在图中做的吧，不是残差图吗？

真的很感激一些帮助，我已经尝试了几个小时来解决这个问题，但我似乎无法理解它。

4

2 回答 2

3

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

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

一个有用的技巧是将k沿边缘的单元vw流表示为afrom vto流和from tow流。这样，您就不必担心增广路径的每个边缘是推动更多的流量向前还是更少的流量向后。如果你这样做，你可以简单地计算剩余容量。-awvvwcap[v][w] - flow[v][w]

有了这种表示，找到一条增广路径就变成了在稠密图中的广度优先搜索，其中有一条边从v到w恰好cap[v][w] > flow[v][w]。这是相当简单的实现。

由于您使用的是 java，因此您应该注意它的每个对象的开销。您描述的 Edge 结构不仅包含两个整数（或指针）和两个双精度数，还包含诸如 GC 信息、一个 klass 指针和一个监视器之类的东西。这是几十个额外的字节，很容易使对象的大小增加一倍或三倍。

当您使代码与稀疏图一起工作时，静态稀疏图的更好表示如下：

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

按“从”顶点对边进行排序。数组的第ith 项from是第一条边的索引，其“from”顶点是第ith 顶点或之后的顶点。最后有一个额外的条目，您应该将其设置为numedges; 当您想要遍历所有边离开给定顶点时，它会派上用场。

由于您正在执行流程，因此您还需要存储后向边缘，所以有一个

int[] rev = new int[numedges];

存储每条边的反向的边索引。现在你可以像这样在边上表示任意函数，比如cap和：flow

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

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

于 2013-05-20T22:14:48.320 回答
2

这是使用深度优先搜索 (DFS) 的 Ford-Fulkerson 方法的实现，该方法使用邻接列表来存储容量。与 Ford-Fulkerson 的邻接矩阵相比，使用邻接列表的棘手部分是您需要自己跟踪剩余边。为了简化事情，我创建了一个处理残差边缘的“addEdge”方法。使用邻接列表而不是邻接矩阵的好处是时间复杂度从O(fV 2 )降低到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<>());
  }

}
于 2017-11-02T05:35:16.110 回答