Ford-Fulkerson算法

提示

基本概念：Ford-Fulkerson算法是一种用于计算流网络中最大可能流的贪婪算法，其中流网络是具有源（S）和汇（T）的顶点和边的网络。
关键术语：算法涉及“增广路径”（流网络中可用的路径）、“剩余图”（表示附加可能流的流网络）和“剩余容量”（边的最大容量减去流量后的容量）。
算法流程：算法从将所有边流量初始化为0开始，然后在源和汇之间存在增广路径时，增加该路径的流量，并更新剩余图，重复这个过程直到找到最大流。

Ford-Fulkerson算法是一种用于计算网络或图中最大可能流的贪婪算法。

术语流网络用于描述具有源（S）和汇（T）的顶点和边的网络。每个顶点，除了S和T外，都可以通过它接收和发送相同数量的流。S只能发送，T只能接收流。

我们可以通过将液体流在不同容量的管道网络中来可视化算法的理解。每根管道在某一时刻可以传输一定数量的液体。对于这个算法，我们要找出在一个时刻从源到汇有多少液体可以通过网络流动。

流网络

使用的术语

增广路径

它是流网络中可用的路径。

剩余图

它表示具有附加可能流的流网络。

剩余容量

这是从最大容量中减去流量后边的容量。

Ford-Fulkerson算法如何工作？

该算法的步骤如下：

将所有边上的流量初始化为0。
当源和汇之间存在增广路径时，将此路径添加到流量中。
更新剩余图。

如果需要，我们还可以考虑反向路径，因为如果不考虑它们，我们可能永远找不到最大流。

上述概念可以通过下面的示例来理解。

Ford-Fulkerson示例

一开始，所有边上的流量都为0。

流网络

选择从S到T的任意路径。在这一步中，我们选择了路径S-A-B-T。

这三条边中的最小容量是2（B-T）。基于此，更新每个路径的流量/容量。
选择另一条路径S-D-C-T。这些边中的最小容量是3（S-D）。

根据此更新容量。
现在，让我们考虑反向路径B-D。选择路径S-A-B-D-C-T。这些边中的最小剩余容量是1（D-C）。

更新容量。

正向路径和反向路径的容量分别考虑。
添加所有流量= 2 + 3 + 1 = 6，这是流网络上可能的最大流量。

请注意，如果任何边的容量已满，则不能使用该路径。

Python、Java和C/C++示例

Python Java C C++

# Python中的Ford-Fulkerson算法

from collections import defaultdict


class Graph:

    def __init__(self, graph):
        self.graph = graph
        self. ROW = len(graph)


    # 使用BFS作为搜索算法
    def searching_algo_BFS(self, s, t, parent):

        visited = [False] * (self.ROW)
        queue = []

        queue.append(s)
        visited[s] = True

        while queue:

            u = queue.pop(0)

            for ind, val in enumerate(self.graph[u]):
                if visited[ind] == False and val > 0:
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        return True if visited[t] else False

    # 应用Ford-Fulkerson算法
    def ford_fulkerson(self, source, sink):
        parent = [-1] * (self.ROW)
        max_flow = 0

        while self.searching_algo_BFS(source

, sink, parent):

            path_flow = float("Inf")
            s = sink
            while(s != source):
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            # 添加路径流量
            max_flow += path_flow

            # 更新边的剩余值
            v = sink
            while(v != source):
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow


graph = [[0, 8, 0, 0, 3, 0],
         [0, 0, 9, 0, 0, 0],
         [0, 0, 0, 0, 7, 2],
         [0, 0, 0, 0, 0, 5],
         [0, 0, 7, 4, 0, 0],
         [0, 0, 0, 0, 0, 0]]

g = Graph(graph)

source = 0
sink = 5

print("最大流量: %d " % g.ford_fulkerson(source, sink))

// 在 Java 中实现 Ford-Fulkerson 算法

import java.util.LinkedList;

class FordFulkerson {
  static final int V = 6;

  // 使用 BFS 作为搜索算法
  boolean bfs(int Graph[][], int s, int t, int p[]) {
    boolean visited[] = new boolean[V];
    for (int i = 0; i < V; ++i)
      visited[i] = false;

    LinkedList<Integer> queue = new LinkedList<Integer>();
    queue.add(s);
    visited[s] = true;
    p[s] = -1;

    while (queue.size() != 0) {
      int u = queue.poll();

      for (int v = 0; v < V; v++) {
        if (visited[v] == false && Graph[u][v] > 0) {
          queue.add(v);
          p[v] = u;
          visited[v] = true;
        }
      }
    }

    return (visited[t] == true);
  }

  // 应用 Ford-Fulkerson 算法
  int fordFulkerson(int graph[][], int s, int t) {
    int u, v;
    int Graph[][] = new int[V][V];

    for (u = 0; u < V; u++)
      for (v = 0; v < V; v++)
        Graph[u][v] = graph[u][v];

    int p[] = new int[V];

    int max_flow = 0;

    // 更新边缘的残留值
    while (bfs(Graph, s, t, p)) {
      int path_flow = Integer.MAX_VALUE;
      for (v = t; v != s; v = p[v]) {
        u = p[v];
        path_flow = Math.min(path_flow, Graph[u][v]);
      }

      for (v = t; v != s; v = p[v]) {
        u = p[v];
        Graph[u][v] -= path_flow;
        Graph[v][u] += path_flow;
      }

      // 添加路径流
      max_flow += path_flow;
    }

    return max_flow;
  }

  public static void main(String[] args) throws java.lang.Exception {
    int graph[][] = new int[][] { { 0, 8, 0, 0, 3, 0 }, { 0, 0, 9, 0, 0, 0 }, { 0, 0, 0, 0, 7, 2 },
        { 0, 0, 0, 0, 0, 5 }, { 0, 0, 7, 4, 0, 0 }, { 0, 0, 0, 0, 0, 0 } };
    FordFulkerson m = new FordFulkerson();

    System.out.println("最大流: " + m.fordFulkerson(graph, 0, 5));

  }
}

/ 在 C 中实现 Ford-Fulkerson 算法

#include <stdio.h>

#define A 0
#define B 1
#define C 2
#define MAX_NODES 1000
#define O 1000000000

int n;
int e;
int capacity[MAX_NODES][MAX_NODES];
int flow[MAX_NODES][MAX_NODES];
int color[MAX_NODES];
int pred[MAX_NODES];

int min(int x, int y) {
  return x < y ? x : y;
}

int head, tail;
int q[MAX_NODES + 2];

void enqueue(int x) {
  q[tail] = x;
  tail++;
  color[x] = B;
}

int dequeue() {
  int x = q[head];
  head++;
  color[x] = C;
  return x;
}

// 使用 BFS 作为搜索算法
int bfs(int start, int target) {
  int u, v;
  for (u = 0; u < n; u++) {
    color[u] = A;
  }
  head = tail = 0;
  enqueue(start);
  pred[start] = -1;
  while (head != tail) {
    u = dequeue();
    for (v = 0; v < n; v++) {
      if (color[v] == A && capacity[u][v] - flow[u][v] > 0) {
        enqueue(v);
        pred[v] = u;
      }
    }
  }
  return color[target] == C;
}

// 应用 Ford-Fulkerson 算法
int fordFulkerson(int source, int sink) {
  int i, j, u;
  int max_flow = 0;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      flow[i][j] = 0;
    }
  }

  // Updating the residual values of edges
  while (bfs(source, sink)) {
    int increment = O;
    for (u = n - 1; pred[u] >= 0; u = pred[u]) {
      increment = min(increment, capacity[pred[u]][u] - flow[pred[u]][u]);
    }
    for (u = n - 1; pred[u] >= 0; u = pred[u]) {
      flow[pred[u]][u] += increment;
      flow[u][pred[u]] -= increment;
    }
    // Adding the path flows
    max_flow += increment;
  }
  return max_flow;
}

int main() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      capacity[i][j] = 0;
    }
  }
  n = 6;
  e = 7;

  capacity[0][1] = 8;
  capacity[0][4] = 3;
  capacity[1][2] = 9;
  capacity[2][4] = 7;
  capacity[2][5] = 2;
  capacity[3][5] = 5;
  capacity[4][2] = 7;
  capacity[4][3] = 4;

  int s = 0, t = 5;
  printf("Max Flow: %d\n", fordFulkerson(s, t));
}

// Ford-Fulkerson algorith in C++

#include <limits.h>
#include <string.h>

#include <iostream>
#include <queue>
using namespace std;

#define V 6

// 使用BFS作为搜索算法
bool bfs(int rGraph[V][V], int s, int t, int parent[]) {
  bool visited[V];
  memset(visited, 0, sizeof(visited));

  queue<int> q;
  q.push(s);
  visited[s] = true;
  parent[s] = -1;

  while (!q.empty()) {
    int u = q.front();
    q.pop();

    for (int v = 0; v < V; v++) {
      if (visited[v] == false && rGraph[u][v] > 0) {
        q.push(v);
        parent[v] = u;
        visited[v] = true;
      }
    }
  }

  return (visited[t] == true);
}

// 应用Ford-Fulkerson算法
int fordFulkerson(int graph[V][V], int s, int t) {
  int u, v;

  int rGraph[V][V];
  for (u = 0; u < V; u++)
    for (v = 0; v < V; v++)
      rGraph[u][v] = graph[u][v];

  int parent[V];
  int max_flow = 0;

  // 更新边的剩余值
  while (bfs(rGraph, s, t, parent)) {
    int path_flow = INT_MAX;
    for (v = t; v != s; v = parent[v]) {
      u = parent[v];
      path_flow = min(path_flow, rGraph[u][v]);
    }

    for (v = t; v != s; v = parent[v]) {
      u = parent[v];
      rGraph[u][v] -= path_flow;
      rGraph[v][u] += path_flow;
    }

    // 添加路径流量
    max_flow += path_flow;
  }

  return max_flow;
}

int main() {
  int graph[V][V] = {{0, 8, 0, 0, 3, 0},
             {0, 0, 9, 0, 0, 0},
             {0, 0, 0, 0, 7, 2},
             {0, 0, 0, 0, 0, 5},
             {0, 0, 7, 4, 0, 0},
             {0, 0, 0, 0, 0, 0}};

  cout << "最大流量: " << fordFulkerson(graph, 0, 5) << endl;
}

Ford-Fulkerson应用

水分配管道
二分图匹配问题
带有需求的流通

Ford-Fulkerson算法

使用的术语​

增广路径​

剩余图​

剩余容量​

Ford-Fulkerson算法如何工作？​

Ford-Fulkerson示例​

Python、Java和C/C++示例​

Ford-Fulkerson应用​