DSA Ford-Fulkerson 算法

Ford-Fulkerson 算法

Ford-Fulkerson 算法用于求解有向图的最大流问题。

流从源顶点 (\(s\)) 发出，到达汇顶点 (\(t\))，并且图中的每条边都有一个由容量限制的流量。

Ford-Fulkerson 算法通过寻找一条具有可用容量从源到汇的路径（称为增广路径），然后通过该路径发送尽可能多的流量来工作。

Ford-Fulkerson 算法会持续寻找新的路径来发送更多流量，直到达到最大流。

在上面的模拟中，Ford-Fulkerson 算法解决了最大流问题：它计算了可以从源顶点 \(s\) 发送到汇顶点 \(t\) 的最大流量，最大流量为 8。

上面模拟中的数字以分数形式显示，第一个数字是流量，第二个数字是容量（该边可能的最大流量）。例如，边 \(s \rightarrow v_2\) 上的 0/7 表示有 0 的流量，容量为 7。

下面是 Ford-Fulkerson 算法工作原理的基本分步描述，但我们需要稍后进行更详细的讲解才能真正理解它。

Ford-Fulkerson 中的残余网络

Ford-Fulkerson 算法实际上是通过创建和使用称为残余网络的内容来工作的，它代表了原始图。

在残余网络中，每条边都有一个残余容量，它等于边的原始容量减去该边的流量。残余容量可以被视为具有一定流量的边的剩余容量。

例如，如果边 \( v_3 \rightarrow v_4 \) 的流量为 2，而容量为 3，则该边的残余流量为 1，因为通过该边还可以发送 1 个单位的流量。

Ford-Fulkerson 中的反向边

Ford-Fulkerson 算法还使用一种称为反向边的机制来反向发送流量。这对于增加总流量很有用。

例如，上面动画中以及下面手动演示中的最后一条增广路径 \(s \rightarrow v_2 \rightarrow v_4 \rightarrow v_3 \rightarrow t\) 表明，通过实际上在边 \( v_4 \rightarrow v_3 \) 上反向发送流量，总流量增加了 1 个单位。

在我们示例中，在边 \( v_3 \rightarrow v_4 \) 上反向发送流量意味着，流出顶点 \( v_3 \) 的这个 1 个单位的流量，现在从边 \( v_3 \rightarrow t \) 离开 \( v_3 \)，而不是从 \( v_3 \rightarrow v_4 \)。

要反向发送流量，与原始边方向相反，为网络中的每条原始边都创建一个反向边。然后，Ford-Fulkerson 算法就可以使用这些反向边来反向发送流量。

反向边没有流量或容量，只有残余容量。反向边的残余容量总是与相应原始边的流量相同。在我们的示例中，边 \( v_3 \rightarrow v_4 \) 的流量为 2，这意味着相应的反向边 \( v_4 \rightarrow v_3 \) 的残余容量为 2。

这仅仅意味着，当原始边 \( v_3 \rightarrow v_4 \) 的流量为 2 时，就可以以相反的方向将相同数量的流量通过该边反向发送。使用反向边推回流量也可以被视为撤销已创建的部分流量。

残余网络的概念（具有边上的残余容量）以及反向边的概念是 Ford-Fulkerson 算法工作原理的核心，我们将在页面下方实现该算法时详细介绍。

手动演练

最初，图中没有流量。

为了找到最大流，Ford-Fulkerson 算法必须增加流量，但首先需要弄清楚流量可以在哪里增加：它必须找到一条增广路径。

Ford-Fulkerson 算法实际上没有规定如何找到这样的增广路径（这就是为什么它经常被描述为一种方法而不是算法），但在本教程中，我们将使用深度优先搜索 (DFS) 来为 Ford-Fulkerson 算法找到增广路径。

Ford-Fulkerson 使用 DFS 找到的第一条增广路径是 \(s \rightarrow v_1 \rightarrow v_3 \rightarrow v_4 \rightarrow t\)。

通过瓶颈计算，Ford-Fulkerson 发现可以通过增广路径发送的最高流量是 3，因此该路径中所有边的流量都增加了 3。

Ford-Fulkerson 算法的下一次迭代是再次执行这些步骤

2. 找到新的增广路径
3. 找出该路径中的流量可以增加多少
4. 相应地增加该路径中边的流量

下一条增广路径被发现是 \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow v_3 \rightarrow t\)，它包括反向边 \(v_4 \rightarrow v_3\)，其中流量被反向发送。

Ford-Fulkerson 的反向边概念非常有用，因为它允许算法的路径查找部分找到一条可以包含反向边的增广路径。

在这种特定情况下，这意味着可以通过边 \(v_3 \rightarrow v_4\) 反向发送 2 个单位的流量，并将其发送到 \(v_3 \rightarrow t\)。

由于 \( v_3 \rightarrow t \) 边的容量限制，该路径的流量只能增加 2。

下一条增广路径被发现是 \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow t\)。

该路径中的流量可以增加 2。瓶颈（限制边）是 \( v_1 \rightarrow v_4 \)，因为该边只剩下发送两个单位流量的空间。

下一条也是最后一条增广路径是 \(s \rightarrow v_2 \rightarrow v_4 \rightarrow t\)。

由于边 \( v_4 \rightarrow t \) 是此路径中的瓶颈，仅剩一个单位流量的空间（\(capacity-flow=1\)），因此此路径的流量只能增加 1。

此时，无法再找到新的增广路径（即找不到可以从 \(s\) 到 \(t\) 发送更多流量的路径），这意味着已找到最大流，Ford-Fulkerson 算法完成。

最大流量为 8。如您在上面的图片中看到的，源顶点 \(s\) 流出的流量（8）与汇顶点 \(t\) 流入的流量相同。

此外，如果您取除了 \(s\) 或 \(t\) 以外的任何其他顶点，您会发现流入该顶点的流量等于流出该顶点的流量。这就是我们所说的流量守恒，对于所有此类流网络（每条边都有流量和容量的有向图），都必须满足此条件。

Ford-Fulkerson 算法的实现

为了实现 Ford-Fulkerson 算法，我们创建一个 Graph 类。 Graph 类表示具有顶点和边的图。

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

第 3 行：我们创建 adj_matrix 来存储所有边和边容量。初始值设置为 0。

第 4 行：size 是图中顶点的数量。

第 5 行：vertex_data 存储所有顶点的名称。

第 7-8 行： add_edge 方法用于添加一条从顶点 u 到顶点 v 的边，容量为 c。

第 10-12 行： add_vertex_data 方法用于向图中添加顶点名称。vertex 参数给出顶点的索引，data 是顶点的名称。

Graph 类还包含 dfs 方法，用于通过深度优先搜索查找增广路径。

    def dfs(self, s, t, visited=None, path=None):
        if visited is None:
            visited = [False] * self.size
        if path is None:
            path = []

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

        if s == t:
            return path

        for ind, val in enumerate(self.adj_matrix[s]):
            if not visited[ind] and val > 0:
                result_path = self.dfs(ind, t, visited, path.copy())
                if result_path:
                    return result_path

        return None

第 15-18 行： visited 数组有助于避免在搜索增广路径时重复访问相同的顶点。属于增广路径的顶点存储在 path 数组中。

第 20-21 行：当前顶点被标记为已访问，然后添加到路径中。

第 23-24 行：如果当前顶点是汇节点，则已找到从源顶点到汇顶点的增广路径，因此可以返回该路径。

第 26-30 行：循环遍历邻接矩阵中的所有边，从当前顶点 s 开始。ind 表示相邻节点，val 是到该顶点的边的残余容量。如果相邻顶点未被访问，并且到该顶点的边有残余容量，则转到该节点并继续从该顶点搜索路径。

第 32 行：如果找不到路径，则返回 None。

我们添加到 Graph 类中的最后一个方法是 fordFulkerson 方法。

    def fordFulkerson(self, source, sink):
        max_flow = 0

        path = self.dfs(source, sink)
        while path:
            path_flow = float("Inf")
            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                path_flow = min(path_flow, self.adj_matrix[u][v])

            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow

            max_flow += path_flow

            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

            path = self.dfs(source, sink)

        return max_flow

最初，max_flow 为 0，并且 while 循环只要存在可以增加流量的增广路径，就会继续增加 max_flow。

第 37 行：找到增广路径。

第 39-42 行：检查增广路径中的每条边，以确定可以通过该路径发送多少流量。

第 44-46 行：由于流量增加，每个正向边的残余容量（容量减去流量）都会减少。

第 47 行：这代表了反向边，Ford-Fulkerson 算法使用它来允许流量被反向发送（撤销）原始正向边。重要的是要理解，这些反向边不在原始图中，它们是 Ford-Fulkerson 引入的虚构边，以使算法能够工作。

第 49 行：每次通过增广路径增加流量时，max_flow 都会增加相同的值。

第 51-52 行：这只是为了在算法开始下一个迭代之前打印增广路径。

定义完 Graph 类后，必须定义顶点和边来初始化特定图，Ford-Fulkerson 算法示例的完整代码如下所示。

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def dfs(self, s, t, visited=None, path=None):
        if visited is None:
            visited = [False] * self.size
        if path is None:
            path = []

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

        if s == t:
            return path

        for ind, val in enumerate(self.adj_matrix[s]):
            if not visited[ind] and val > 0:
                result_path = self.dfs(ind, t, visited, path.copy())
                if result_path:
                    return result_path

        return None

    def fordFulkerson(self, source, sink):
        max_flow = 0

        path = self.dfs(source, sink)
        while path:
            path_flow = float("Inf")
            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                path_flow = min(path_flow, self.adj_matrix[u][v])

            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow

            max_flow += path_flow

            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

            path = self.dfs(source, sink)

        return max_flow

g = Graph(6)
vertex_names = ['s', 'v1', 'v2', 'v3', 'v4', 't']
for i, name in enumerate(vertex_names):
    g.add_vertex_data(i, name)

g.add_edge(0, 1, 3)  # s  -> v1, cap: 3
g.add_edge(0, 2, 7)  # s  -> v2, cap: 7
g.add_edge(1, 3, 3)  # v1 -> v3, cap: 3
g.add_edge(1, 4, 4)  # v1 -> v4, cap: 4
g.add_edge(2, 1, 5)  # v2 -> v1, cap: 5
g.add_edge(2, 4, 3)  # v2 -> v4, cap: 3
g.add_edge(3, 4, 3)  # v3 -> v4, cap: 3
g.add_edge(3, 5, 2)  # v3 -> t,  cap: 2
g.add_edge(4, 5, 6)  # v4 -> t,  cap: 6

source = 0; sink = 5

print("The maximum possible flow is %d " % g.fordFulkerson(source, sink))

Ford-Fulkerson 算法的时间复杂度

Ford-Fulkerson 的时间复杂度因顶点数 \(V\)、边数 \(E\) 以及实际上图中的最大流 \(f\) 而异。

时间复杂度之所以会随图中最大流 \(f\) 而变化，是因为在吞吐量很大的图中，会有更多的增广路径来增加流量，这意味着查找这些增广路径的 DFS 方法需要运行更多次。

深度优先搜索 (DFS) 的时间复杂度为 \(O(V+E)\)。

DFS 每次运行一次，代表一条新的增广路径。如果我们假设每条增广图都增加 1 个单位的流量，DFS 就必须运行 \(f\) 次，即最大流量值次数。

这意味着，使用 DFS 的 Ford-Fulkerson 算法的时间复杂度为

\[ O( (V+E) \cdot f ) \]

对于稠密图，其中 \( E > V \)，DFS 的时间复杂度可以简化为 \(O(E)\)，这意味着 Ford-Fulkerson 算法的时间复杂度也可以简化为

\[ O( E \cdot f ) \]

稠密图没有精确的定义，但它是一种边很多的图。

我们将描述的下一个查找最大流的算法是Edmonds-Karp 算法。

Edmonds-Karp 算法与 Ford-Fulkerson 非常相似，但它使用 BFS 而不是 DFS 来查找增广路径，从而减少了查找最大流的迭代次数。