C++ Edmonds Karp 算法

2024年8月28日 | 阅读 12 分钟

Edmonds-Karp 算法 是一种强大而高效的方法，用于在流网络中查找最大流。流网络是有向图，其中每条边都有一个容量，表示其能承载的最大流量。该算法建立在 Ford-Fulkerson 方法的基础上，但改进了其最坏情况时间复杂度。

Edmonds-Karp 算法的核心是使用广度优先搜索 (BFS) 来查找残余图中的增广路径。残余图是原始图的修改版本，反映了在当前流量发送后每条边上剩余的容量。通过反复查找增广路径并更新这些路径上的流量，算法收敛到最大流。

关键洞察

Edmonds-Karp 的关键见解是，使用 BFS 查找增广路径可确保首先考虑边数最少的路径。这导致最坏情况时间复杂度为 O(VE^2)，其中 V 是顶点数，E 是边数。使用 BFS 可确保每条增广路径的长度最多为 O(VE)，从而避免了在原始 Ford-Fulkerson 方法中任意选择增广路径可能出现的无限循环问题。

算法以零初始流量开始，并反复增加流量，直到找不到更多增广路径为止。在每次迭代中，使用 BFS 来发现具有可用容量的增广路径。然后确定该路径的瓶颈容量，并相应地更新该路径上的流量。此过程一直持续到不再存在增广路径，从而达到最大流量。

Edmonds-Karp 因其简洁性、正确性以及多项式时间复杂度的保证而成为一种被广泛采用的算法。虽然存在更先进的最大流算法，但 Edmonds-Karp 在图的大小可管理的情况下，仍然是教学目的和实际应用的绝佳选择。该算法对 BFS 的依赖使其特别适合稠密图或边容量相对较低的图。

历史

Edmonds-Karp 算法是计算机科学和图论领域的一项重要发展，专门用于解决网络流分析中的最大流问题。该算法以其发明者 Jack Edmonds 和 Richard Karp 命名，并于 1972 年首次发表。

该算法的历史与 20 世纪中叶日益突出的网络流问题有着密切的联系。在 20 世纪 40 年代末 和 50 年代，像 George Dantzig 和 T.C. Koopmans 这样的研究人员探索了与网络中的运输和流量相关的问题。最大流的概念，即确定可以通过网络运输的物料的最大量，成为一个中心焦点。

在 20 世纪 70 年代初，Jack Edmonds 和 Richard Karp 独立地研究了最大流问题。Edmonds 此前在拟阵论和优化方面做出了重要贡献，而 Karp 则以其在复杂性理论和算法方面的工作而闻名。他们的合作催生了 Edmonds-Karp 算法，这是 L.R. Ford Jr. 和 D.R. Fulkerson 于 1956 年提出的 Ford-Fulkerson 算法 的一个改进。

Edmonds-Karp 算法采用了增广路径的思想，其中残余容量在网络中沿着从源到汇的路径增加。Edmonds-Karp 的独特之处在于它使用广度优先搜索 (BFS) 来高效地查找增广路径。这确保了算法的最坏情况时间复杂度是多项式的，具体为 O(VE^2)，使其比原始 Ford-Fulkerson 算法更具可预测性和可靠性。

该算法的引入标志着算法设计和图论的一个重要里程碑，为最大流问题提供了更鲁棒的解决方案。多年来，它已在包括运输、通信网络和运筹学在内的各个领域得到应用。其历史意义不仅在于其效率，还在于其对后续网络流算法及相关优化问题研究的影响。

示例

下面是 C++ 中 Edmonds Karp 算法的实现

#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int INF = INT_MAX;
const int MAX_V = 100; // Adjust this according to your maximum number of vertices
int capacity[MAX_V][MAX_V];
int parent[MAX_V];
int bfs(int source, int sink, vector<vector<int>> &graph) {
 fill(parent, parent + MAX_V, -1);
 parent[source] = source;
 queue<pair<int, int>> q;
 q.push({source, INF});
 while (!q.empty()) {
 int current = q.front().first;
 int flow = q.front().second;
 q.pop();
 for (int next : graph[current]) {
 if (parent[next] == -1 && capacity[current][next] > 0) {
 parent[next] = current;
 int new_flow = min(flow, capacity[current][next]);
 if (next == sink)
 return new_flow;
 q.push({next, new_flow});
 }
 }
 }
 return 0;
}
int edmondsKarp(int source, int sink, vector<vector<int>> &graph) {
 int max_flow = 0;
 int new_flow;
 while ((new_flow = bfs(source, sink, graph)) > 0) {
 max_flow += new_flow;
 int current = sink;
 while (current != source) {
 int prev = parent[current];
 capacity[prev][current] -= new_flow;
 capacity[current][prev] += new_flow;
 current = prev;
 }
 }
 return max_flow;
}
int main() {
 // Example usage:
 int source = 0;
 int sink = 5;
 vector<vector<int>> graph(MAX_V);
 // Add directed edges with capacities
 capacity[0][1] = 10;
 capacity[0][2] = 5;
 capacity[1][2] = 15;
 capacity[1][3] = 5;
 capacity[2][3] = 10;
 capacity[2][4] = 10;
 capacity[3][4] = 5;
 capacity[3][5] = 10;
 capacity[4][5] = 10;
 // Create adjacency list representation
 for (int i = 0; i < MAX_V; ++i) {
 for (int j = 0; j < MAX_V; ++j) {
 if (capacity[i][j] > 0) {
 graph[i].push_back(j);
 }
 }
 }
 int max_flow = edmondsKarp(source, sink, graph);
 cout << "Maximum Flow: " << max_flow << endl;
 return 0;
}

输出

Maximum Flow: 20
.................................
Process executed in 1.11 seconds
Press any key to continue

说明

包含语句
- #include <iostream>: 包含用于输入输出操作的输入输出流库。
- #include <climits>: 包含用于使用 INT_MAX 的极限库
- #include <cstring>: 包含用于字符串相关函数的 C 字符串库。
- #include <queue>: 包含用于使用队列的队列库。
- #include <vector>: 包含用于动态数组实现的 vector 库。
命名空间声明
- using namespace std;: 指示使用 std (标准) 命名空间以简化代码引用。
常量声明
- const int INF = INT_MAX;: 定义一个常量 INF，其值为整数的最大可能值。
- const int MAX_V = 100;: 定义一个常量 MAX_V 作为顶点的最大数量 (请根据您的需求进行调整)。
全局变量
- int capacity[MAX_V][MAX_V];: 定义一个二维数组来存储图中边的容量。
- int parent[MAX_V];: 定义一个数组来存储 BFS 遍历期间每个顶点的父节点。
BFS 函数
- int bfs(int source, int sink, vector<vector<int>> &graph) { ... }: 实现广度优先搜索以在图中查找增广路径。
- 将父节点数组填充为 -1，表示最初没有父节点。
- 使用队列遍历图并查找增广路径。
Edmonds-Karp 函数
- int edmondsKarp(int source, int sink, vector<vector<int>> &graph) { ... }: 实现 Edmonds-Karp 算法来查找最大流。
- 循环调用 bfs 函数，直到找不到更多增广路径为止。
- 更新容量并返回最大流。
主函数
- int main() { ... }: 程序的入口点。
- Edmonds-Karp 算法的示例用法。
- 初始化源和汇顶点。
- 根据 capacity 矩阵中定义的容量创建邻接表表示 (graph)。
- 调用 edmondsKarp 函数查找最大流。
- 打印结果。
示例用法
- int source = 0;: 设置流网络的源顶点。
- int sink = 5;: 设置流网络的汇顶点。
- 根据 capacity 矩阵中定义的容量创建邻接表表示 (graph)。
- 添加具有容量的有向边。
- 调用 edmondsKarp 函数查找并打印最大流。
图初始化
- 遍历 capacity 矩阵以填充邻接表表示 (graph)。
- 如果顶点之间的容量大于 0，则将边添加到邻接表中。
输出
- cout << "Maximum Flow: " << max_flow << endl;: 打印 Edmonds-Karp 算法计算出的最大流。

时间和空间复杂度分析

Edmonds-Karp 算法是 Ford-Fulkerson 方法的一个变体，用于在网络中查找最大流。以下是所提供 C++ 代码的时间和空间复杂度分析。

时间复杂度

广度优先搜索 (BFS): 算法的主循环由一系列 BFS 操作组成，每个 BFS 操作以层级方式遍历图。在邻接表表示的图上，BFS 的最坏情况时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。在每次迭代中，BFS 用于从源到汇查找增广路径。
迭代次数: 在最坏情况下，Edmonds-Karp 算法可能需要迭代残余图中的所有边，直到找不到增广路径为止。在每次迭代中，都会应用 BFS，而 BFS 需要 O(V + E) 时间，因此算法的最坏情况时间复杂度为 O(VE^2)，其中 V 是顶点数，E 是边数。
容量更新: 在每次迭代中，算法都会更新沿增广路径的残余图的容量。更新容量对于每条边需要恒定的时间。

总而言之，Edmonds-Karp 算法的时间复杂度在最坏情况下由 BFS 操作主导，结果为 O(VE^2)。

空间复杂度

图表示: 空间复杂度主要由图表示决定。在此实现中，使用邻接表来表示图。邻接表存储在 graph vector 中，其大小为 O(V + E)，其中 V 是顶点数，E 是边数。
父节点数组: 父节点数组用于追溯 BFS 找到的增广路径。父节点数组的大小为 O(V)，其中 V 是顶点数。
容量矩阵: 容量矩阵表示图中边的容量。其大小为 O(V^2)，其中 V 是顶点数。
队列: BFS 算法使用队列来跟踪要访问的顶点。在最坏情况下，所有顶点都可能入队，导致空间复杂度为 O(V)。
考虑到所有这些组件，Edmonds-Karp 算法的总空间复杂度为 O(V + E)。

总而言之，Edmonds-Karp 算法为在流网络中查找最大流提供了多项式时间解决方案。对于中小型图，其时间复杂度是合理的，其空间复杂度也易于管理。然而，对于大型图，更先进的算法（如 Push-Relabel 算法）可能更适合。

Edmonds Karp 算法的应用

Edmonds-Karp 算法 是 Ford-Fulkerson 算法的一个变体，由于其在解决最大流问题方面的效率，已在各个领域得到广泛应用。以下是一些值得注意的应用：

网络流优化

Edmonds-Karp 算法 的主要应用是网络流优化。它广泛应用于交通和物流中，用于对货物流进行建模和优化，确保资源的有效利用并最大限度地降低运输成本。

通信网络

在通信网络（例如互联网）的设计和管理中，可以使用 Edmonds-Karp 算法来优化数据流。它有助于确定可以通过不同路由传输的最大数据量，从而提高网络效率。

计算系统中的资源分配

该算法用于计算系统中优化资源分配。在多个进程或应用程序争夺资源的情况下，Edmonds-Karp 有助于以最大化整体系统性能的方式分配资源。

水和能源分配

在供水和能源分配网络中，可以使用该算法来优化资源流，确保水和能源高效地到达目的地。这对于城市规划和管理稀缺资源至关重要。

供应链管理

Edmonds-Karp 应用于供应链管理，以优化通过分销网络的货物流。它有助于确定将商品从制造商运输到消费者的最有效路线，从而最大限度地降低成本并最大限度地提高吞吐量。

图像分割

在计算机视觉领域，该算法已被改编用于图像分割。通过将像素视为节点并使用该算法查找最大流路径，它有助于识别和分离图像中的不同对象。

生物和医学应用

该算法应用于生物研究，用于模拟人体血液循环等过程。在医学成像中，它有助于分析和优化造影剂或其他物质在生物系统中的流动。

博弈论

Edmonds-Karp 已应用于博弈论中某些问题的建模和求解，特别是在涉及玩家之间的策略互动和资源分配的情况下。

总而言之，Edmonds-Karp 算法的多功能性使其在各种应用中得到采用，为各个领域提供了更有效和优化的解决方案。其高效处理网络流问题的能力使其成为理论研究和实际实现中的宝贵工具。

优点和缺点

Edmonds-Karp 算法是 Ford-Fulkerson 算法 的一个扩展，是用于在流网络中查找最大流的常用方法。流网络在各种应用中至关重要，例如运输系统、通信网络和资源分配。Edmonds-Karp 算法与任何算法一样，都有其优点和缺点，我们将对此进行详细探讨。

优点

1. 保证收敛

Edmonds-Karp 算法的关键优势之一是它能在有限的迭代次数内保证收敛到最大流。这是因为使用了最短可能长度的增广路径，从而确保算法能够高效地终止。

2. 多项式时间复杂度

Edmonds-Karp 算法具有多项式时间复杂度 O(VE^2)，其中 V 是顶点数，E 是边数。这种多项式时间复杂度使其比其他一些最大流算法更有效，尤其是在稀疏图中。

3. 易于实现

该算法实现起来相对简单，易于开发人员和研究人员使用。其简洁性使其在学术和实际应用中都非常受欢迎。

4. 广度优先搜索 (BFS) 方法

Edmonds-Karp 采用 广度优先搜索 (BFS) 策略来查找增广路径。这可确保首先考虑最短的增广路径，从而在实践中更快地收敛。

5. 适用于二分匹配

该算法可以改编用于高效地解决最大二分匹配问题。这使其具有多功能性，因为二分匹配在诸如作业分配、资源分配和网络流等领域都有应用。

6. 具有整数容量的网络流

Edmonds-Karp 在所有容量均为整数的情况下表现良好。在分数容量可能无意义的应用中，例如道路上的汽车数量或通信链路的容量，这是一个重要的考虑因素。

缺点

1. 空间复杂度

该算法需要为每条边存储残余容量。在稠密图或容量大的网络中，空间复杂度可能成为一个问题。当处理顶点和边数量很多的网络时，这一点尤为重要。

2. 依赖于整数容量

虽然 Edmonds-Karp 在整数容量方面效果很好，但在容量是实数或涉及浮点运算的情况下，其性能可能不是最优的。在这种情况下，舍入误差可能会影响结果的准确性。

3. 易受大容量影响

当处理具有大容量的网络时，该算法的时间复杂度可能变得不切实际。时间复杂度中的平方因子 (O(VE^2)) 可能导致更长的计算时间，尤其是在 E 很大的情况下。

4. 对小流量网络非最优

在最大流量远小于网络总流量容量的网络中，该算法可能有点大材小用。在这些情况下，存在更专业的算法可以更好地执行。

5. 依赖 BFS 进行路径选择

虽然 BFS 可确保收敛，但它可能不总是选择最优的增广路径。在某些情况下，它可能导致次优流量，尤其是在存在容量更大的替代路径时。

6. 对输入顺序敏感

处理边的顺序会影响算法的性能。在某些情况下，不同的输入顺序可能导致不同的运行时间，从而影响结果的可重复性。

结论

总之，Edmonds-Karp 算法 具有几个优点，包括保证终止、在稀疏图中实践中的效率、最优性、多功能性以及简单的残余图表示。然而，在选择特定应用的算法时，应考虑其在稠密图上的性能、空间复杂度、对初始流量的敏感性以及对非整数容量和负边权重的限制。在确定 Edmonds-Karp 算法或替代方法的适用性时，必须权衡这些因素与所分析的特定流网络的特性和要求。

下一个主题C++ 中的 fallthrough

C++ Edmonds Karp 算法

关键洞察

历史

示例

时间和空间复杂度分析

Edmonds Karp 算法的应用

优点和缺点

优点

缺点

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ Edmonds Karp 算法

关键洞察

历史

示例

时间和空间复杂度分析

Edmonds Karp 算法的应用

优点和缺点

优点

缺点

结论

相关帖子

C++ 有序映射

C++ 用户定义大小的二维向量

C++ 命名约定

何时按引用或指针传递参数

C++ 重新抛出异常

C++ 数字转字符程序

C++ multimap key_comp()

C++ seekg() 函数

C++ 程序计算数组中的正数和负数个数

C++ AES 算法

订阅 Tpoint Tech