DSA Edmonds-Karp 算法
Edmonds-Karp 算法解决了最大流问题。
寻找最大流在许多领域都很有帮助：优化网络流量、制造业、供应链和物流，或航空公司调度。
Edmonds-Karp 算法
Edmonds-Karp 算法解决了有向图的最大流问题。
流量从源点 (\(s\)) 流出，终止于汇点 (\(t\))，图中的每条边都允许一个流量，受容量限制。
Edmonds-Karp 算法与 Ford-Fulkerson 算法非常相似，不同之处在于 Edmonds-Karp 算法使用 广度优先搜索 (BFS) 来寻找增广路径以增加流量。
最大流：{{maxFlow}}
{{statusText}}Edmonds-Karp 算法通过使用广度优先搜索 (BFS) 找到一条从源点到汇点具有可用容量的路径（称为增广路径），然后通过该路径发送尽可能多的流量。
Edmonds-Karp 算法会持续寻找新的路径以发送更多流量，直到达到最大流量。
在上面的模拟中，Edmonds-Karp 算法解决了最大流问题：它找出可以从源点 \(s\) 发送到汇点 \(t\) 的最大流量，该最大流量为 8。
上面模拟中的数字以分数形式书写，其中第一个数字是流量，第二个数字是容量（该边的最大可能流量）。因此，例如，边 \(s \rightarrow v_2\) 上的 0/7 意味着该边上流量为 0，容量为 7。
您可以在下面看到 Edmonds-Karp 算法工作原理的基本分步描述，但我们需要稍后深入了解更多细节才能真正理解它。
工作原理
- 所有边的初始流量均为零。
- 使用 BFS 寻找一条可以发送更多流量的增广路径。
- 进行瓶颈计算以找出可以通过该增广路径发送多少流量。
- 增加通过瓶颈计算找到的每条增广路径上的流量。
- 重复步骤 2-4，直到找到最大流。当无法再找到新的增广路径时，就会发生这种情况。
Edmonds-Karp 中的残余网络
Edmonds-Karp 算法通过创建和使用一种称为残余网络的东西来工作，它是原始图的表示。
在残余网络中，每条边都具有残余容量，即边的原始容量减去该边中的流量。残余容量可以看作是带有一定流量的边中剩余的容量。
例如，如果边 \( v_3 \rightarrow v_4 \) 中有 2 单位流量，容量为 3，则该边的残余流量为 1，因为该边中还有空间可以发送 1 单位流量。
Edmonds-Karp 中的反向边
Edmonds-Karp 算法还使用反向边来回送流量。这有助于增加总流量。
为了回送流量（与边的方向相反），为网络中的每条原始边创建一个反向边。Edmonds-Karp 算法然后可以使用这些反向边以相反方向发送流量。
反向边没有流量或容量，只有残余容量。反向边的残余容量总是与相应原始边中的流量相同。
在我们的例子中，边 \( v_1 \rightarrow v_3 \) 有 2 单位流量，这意味着相应反向边 \( v_3 \rightarrow v_1 \) 上有 2 单位残余容量。
这仅仅意味着当原始边 \( v_1 \rightarrow v_3 \) 上有 2 单位流量时，有可能在该边上回送相同数量的流量，但方向相反。使用反向边回推流量也可以看作是撤消已经创建的流量的一部分。
具有边上残余容量的残余网络的概念，以及反向边的概念，是 Edmonds-Karp 算法工作原理的核心，我们将在本页进一步实现该算法时详细讨论这一点。
手动演练
图中最初没有流量。
Edmonds-Karp 算法首先使用广度优先搜索来寻找可以增加流量的增广路径，即 \(s \rightarrow v_1 \rightarrow v_3 \rightarrow t\)。
找到增广路径后，进行瓶颈计算以确定可以通过该路径发送多少流量，该流量为：2。
因此，在增广路径中的每条边上发送 2 单位流量。
Edmonds-Karp 算法的下一次迭代是再次执行这些步骤：找到新的增广路径，找出该路径中的流量可以增加多少，并相应地增加该路径中边的流量。
发现下一条增广路径是 \(s \rightarrow v_1 \rightarrow v_4 \rightarrow t \)。
此路径中的流量只能增加 1 单位，因为 \( s \rightarrow v_1 \) 边中只剩下 1 单位流量的空间。
发现下一条增广路径是 \(s \rightarrow v_2 \rightarrow v_4 \rightarrow t\)。
此路径中的流量可以增加 3 单位。瓶颈（限制边）是 \( v_2 \rightarrow v_4 \)，因为容量为 3。
找到的最后一条增广路径是 \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow t\)。
此路径中的流量只能增加 2 单位，因为边 \( v_4 \rightarrow t \) 是此路径中的瓶颈，只剩下 2 单位流量的空间（\(容量-流量=1\)）。
此时，无法找到新的增广路径（无法找到从 \(s\) 到 \(t\) 可以发送更多流量的路径），这意味着已找到最大流量，并且 Edmonds-Karp 算法完成。
最大流量为 8。如上图所示，从源点 \(s\) 流出的流量 (8) 与流入汇点 \(t\) 的流量相同。
此外，如果您选择除 \(s\) 或 \(t\) 之外的任何其他顶点，您会发现流入顶点的流量与流出顶点的流量相同。这就是我们所说的流量守恒，这必须适用于所有此类流量网络（每条边都有流量和容量的有向图）。
Edmonds-Karp 算法的实现
为了实现 Edmonds-Karp 算法，我们创建了一个 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 类还包含 bfs 方法，用于使用广度优先搜索查找增广路径
def bfs(self, s, t, parent):
visited = [False] * self.size
queue = [] # Using list as a queue
queue.append(s)
visited[s] = True
while queue:
u = queue.pop(0) # Pop from the start of the list
for ind, val in enumerate(self.adj_matrix[u]):
if not visited[ind] and val > 0:
queue.append(ind)
visited[ind] = True
parent[ind] = u
return visited[t]第 15-18 行：visited 数组有助于在搜索增广路径时避免重复访问相同的顶点。queue 存储待探索的顶点，搜索总是从源点 s 开始。
第 20-21 行：只要 queue 中有待探索的顶点，就从 queue 中取出第一个顶点，以便可以从那里找到到下一个顶点的路径。
第 23 行：对于当前顶点的每个相邻顶点。
第 24-27 行：如果相邻顶点尚未被访问，并且到该顶点的边上存在残余容量：将其添加到待探索的顶点队列中，标记为已访问，并将相邻顶点的 parent 设置为当前顶点 u。
parent 数组存储顶点的父节点，从而创建从汇点反向到源点的路径。parent 稍后在 Edmonds-Karp 算法中（在 bfs 方法之外）用于增加增广路径中的流量。
第 29 行：最后一行返回 visited[t]，如果增广路径终止于汇点 t，则该值为 true。返回 true 意味着已找到增广路径。
edmonds_karp 方法是我们添加到 Graph 类的最后一个方法
def edmonds_karp(self, source, sink):
parent = [-1] * self.size
max_flow = 0
while self.bfs(source, sink, parent):
path_flow = float("Inf")
s = sink
while(s != source):
path_flow = min(path_flow, self.adj_matrix[parent[s]][s])
s = parent[s]
max_flow += path_flow
v = sink
while(v != source):
u = parent[v]
self.adj_matrix[u][v] -= path_flow
self.adj_matrix[v][u] += path_flow
v = parent[v]
path = []
v = sink
while(v != source):
path.append(v)
v = parent[v]
path.append(source)
path.reverse()
path_names = [self.vertex_data[node] for node in path]
print("Path:", " -> ".join(path_names), ", Flow:", path_flow)
return max_flow最初，parent 数组包含无效索引值，因为开始时没有增广路径，并且 max_flow 为 0，while 循环会不断增加 max_flow，只要有增广路径可以增加流量。
第 35 行：外部 while 循环确保 Edmonds-Karp 算法在有增广路径可供增加流量时继续增加流量。
第 36-37 行：增广路径上的初始流量是无限的，并且可能的流量增加将从汇点开始计算。
第 38-40 行：path_flow 的值通过从汇点反向遍历到源点来找到。沿路径的残余容量的最小值决定了路径上可以发送多少流量。
第 42 行：path_flow 会增加 path_flow。
第 44-48 行：遍历增广路径，从汇点反向到源点，前向边上的残余容量会因 path_flow 减少，而反向边上的残余容量会因 path_flow 增加。
第 50-58 行：这部分代码仅用于打印，以便我们能够跟踪每次找到增广路径以及通过该路径发送的流量。
定义 Graph 类之后，必须定义顶点和边以初始化特定的图，Edmonds-Karp 算法示例的完整代码如下所示
示例
Python
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 bfs(self, s, t, parent):
visited = [False] * self.size
queue = [] # Using list as a queue
queue.append(s)
visited[s] = True
while queue:
u = queue.pop(0) # Pop from the start of the list
for ind, val in enumerate(self.adj_matrix[u]):
if not visited[ind] and val > 0:
queue.append(ind)
visited[ind] = True
parent[ind] = u
return visited[t]
def edmonds_karp(self, source, sink):
parent = [-1] * self.size
max_flow = 0
while self.bfs(source, sink, parent):
path_flow = float("Inf")
s = sink
while(s != source):
path_flow = min(path_flow, self.adj_matrix[parent[s]][s])
s = parent[s]
max_flow += path_flow
v = sink
while(v != source):
u = parent[v]
self.adj_matrix[u][v] -= path_flow
self.adj_matrix[v][u] += path_flow
v = parent[v]
path = []
v = sink
while(v != source):
path.append(v)
v = parent[v]
path.append(source)
path.reverse()
path_names = [self.vertex_data[node] for node in path]
print("Path:", " -> ".join(path_names), ", Flow:", path_flow)
return max_flow
# Example usage:
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.edmonds_karp(source, sink))Edmonds-Karp 算法的时间复杂度
Edmonds-Karp 和 Ford-Fulkerson 的区别在于 Edmonds-Karp 使用广度优先搜索（BFS）来寻找增广路径，而 Ford-Fulkerson 使用深度优先搜索（DFS）。
这意味着 Edmonds-Karp 的运行时间比 Ford-Fulkerson 更容易预测，因为 Edmonds-Karp 不受最大流值的影响。
设顶点数为 \(V\)，边数为 \(E\)，Edmonds-Karp 算法的时间复杂度为
\[ O(V \cdot E^2) \]
这意味着 Edmonds-Karp 不像 Ford-Fulkerson 那样依赖于最大流，而是依赖于我们拥有的顶点和边的数量。
Edmonds-Karp 获得此时间复杂度的原因是它运行 BFS，其时间复杂度为 \(O(E+V)\)。
但如果我们假设 Edmonds-Karp 的最坏情况，即一个稠密图，其中边数 \(E\) 远大于顶点数 \(V\)，则 BFS 的时间复杂度变为 \(O(E)\)。
BFS 必须为每个增广路径运行一次，并且在 Edmonds-Karp 算法运行期间实际上可以找到接近 \(V \cdot E \) 个增广路径。
因此，时间复杂度为 \(O(E)\) 的 BFS 在最坏情况下可以运行接近 \(V \cdot E \) 次，这意味着 Edmonds-Karp 的总时间复杂度为：\( O(V \cdot E \cdot E) = O(V \cdot E^2) \)。
