6 网络流算法基础

在图算法系列的上一篇中，我们详细探讨了图的最小生成树，包括了常用的 Kruskal 和 Prim 算法。在本篇中，我们将深入了解一个重要的图算法——网络流算法，特别是在解决实际问题中的应用。

网络流算法的核心概念是如何在一个流网络中从源点流向汇点（也称终点）以最优化地利用资源。我们将通过案例学习基本的网络流问题，以及如何使用 Ford-Fulkerson 算法来解决这一问题。

网络流基本概念

在网络流中，我们要处理一个有向图，它包括以下几个组成部分：

• 节点：代表图中的顶点，包括源点 $s$ 和汇点 $t$。
• 边：每条边都有一个非负的容量，用来表示流动的最大限制。
• 流：表示从源点到汇点沿边流动的量，流的量不能超过边的容量。

流的定义

在网络流中，流 $f(u, v)$ 代表从节点 $u$ 到节点 $v$ 的流量，满足以下条件：

1. 容量限制：对于每条边 $(u, v)$，都有 $f(u, v) \leq c(u, v)$，其中 $c(u, v)$ 是边的容量。
2. 流量守恒：对于每个中间节点 $u$，流入和流出的流量必须相等，即：
   $$
   \sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)
   $$
   对于源点 $s$，流入为 0；对于汇点 $t$，流出为 0。

Ford-Fulkerson 算法

接下来，我们将介绍 Ford-Fulkerson 方法，这是解决网络流问题的经典算法。该算法通过增广路径来找到最大流。

算法步骤

1. 初始化流：开始时，所有边的流量 $f(u, v) = 0$。
2. 查找增广路径：在残量网络中使用深度优先搜索（DFS）或广度优先搜索（BFS）寻找从源点 $s$ 到汇点 $t$ 的增广路径。
3. 调整流：对找到的路径，计算路径上的最小剩余容量，并将该容量加到路径上的所有边的流量上。
4. 更新残量网络：更新边的容量和反向边的流量，直到无法再找到增广路径为止。

示例

我们来看一个具体的例子来说明 Ford-Fulkerson 算法的使用。

示例图

假设我们有以下网络：

   10
(s)----->(A)
 |       /| \
 |      / |  \
 |     /  |   \ 10
5|    /   |    \
 |   /    |     \
 v  v     v      v
(B)----->(C)---->(t)
   15      10

在这个图中，源点是 $s$，汇点是 $t$，边的容量分别为上图所示。

实现算法

我们可以用 Python 来实现该算法，以下是一个简单的代码示例：

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)  # 存储图的结构
        self.capacity = {}               # 存储边的容量

    def add_edge(self, u, v, cap):
        self.graph[u].append(v)
        self.graph[v].append(u)  # 创建反向边
        self.capacity[(u, v)] = cap
        self.capacity[(v, u)] = 0  # 初始化反向边的容量为 0

    def bfs(self, s, t, parent):
        visited = set()
        queue = deque([s])
        visited.add(s)

        while queue:
            u = queue.popleft()

            for v in self.graph[u]:
                if v not in visited and self.capacity[(u, v)] > 0:
                    visited.add(v)
                    parent[v] = u
                    queue.append(v)

        return t in visited

    def ford_fulkerson(self, s, t):
        parent = {}
        max_flow = 0

        while self.bfs(s, t, parent):
            path_flow = float('Inf')
            v = t

            while v != s:
                u = parent[v]
                path_flow = min(path_flow, self.capacity[(u, v)])
                v = parent[v]

            v = t
            while v != s:
                u = parent[v]
                self.capacity[(u, v)] -= path_flow
                self.capacity[(v, u)] += path_flow
                v = parent[v]

            max_flow += path_flow

        return max_flow

# 使用示例
g = Graph()
g.add_edge('s', 'A', 10)
g.add_edge('s', 'B', 5)
g.add_edge('A', 'C', 10)
g.add_edge('B', 'C', 15)
g.add_edge('C', 't', 10)

max_flow = g.ford_fulkerson('s', 't')
print(f"最大流为: {max_flow}")

在这个示例中，我们创建了一个带有指定边和容量的流网络，然后通过 Ford-Fulkerson 算法计算出最大流。运行上述代码，输出将显示最大流的值。

总结

网络流算法是算法设计和优化中的重要工具，能够解决许多实际问题，如最大流、最小割等。通过 Ford-Fulkerson 算法的学习，我们可以建立起理解更为复杂的流网络问题的基础。

在下一篇中，我们将探讨动态规划的进阶思想与应用，涉及如何利用动态规划解决更复杂的问题。希望大家保持兴趣，继续深入学习！