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。
上面模拟中的数字以分数形式写出，其中第一个数字是流量，第二个数字是容量（该边上的最大可能流量）。例如，0/7 在边 \(s \rightarrow v_2\) 上，表示在该边上流量为 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 \) 边上只有一格空间可以容纳一个单位的流量。
发现下一条增广路径是 \(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 个单位的空间可以容纳更多流量 (\(capacity-flow=1\))。
此时，无法找到新的增广路径（无法找到一条可以从 \(s\) 到 \(t\) 发送更多流量的路径），这意味着已经找到了最大流，Edmonds-Karp 算法完成。
最大流为 8。如上图所示，流出源顶点 \(s\) 的流量 (8) 与流入汇点顶点 \(t\) 的流量相同。
此外，如果您选择除 \(s\) 或 \(t\) 之外的任何其他顶点，您会发现流入该顶点的流量与流出该顶点的流量相同。这就是我们所说的流量守恒，对于所有此类流量网络（每条边都有流量和容量的有向图）都必须满足该条件。
Edmonds-Karp 算法的实现
为了实现 Edmonds-Karp 算法，我们创建了一个 Graph 类。
The 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 是顶点的名称。
The 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 数组有助于在搜索增广路径时避免重复访问相同的顶点。The 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，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) \)。
