C++ Ford Fulkerson 算法

2025年3月21日 | 阅读 6 分钟

在本文中，我们将讨论 C++ 中的 Ford Fulkerson 算法及其实现。

什么是 Ford Fulkerson 算法？

Ford-Fulkerson 算法常用于解决流中的最大流问题。最大流问题关注的是，在一个有方向的加权图中，在考虑边容量限制的情况下，可以从给定源点传输到汇点的最大流量。该技术通过迭代地在残余图中识别一条连接起点和汇点的增强路径来操作。残余图是通过从每条边的容量中减去当前数据流而创建的。然后，该程序沿此路径增加尽可能大的流量，该流量等于该路径上边的最小容量。

问题

考虑一个表示流网络的图，每条边都有容量值。此外，给定网络中的两个顶点，源点“s”和汇点“t”，在一些约束条件下确定从 s 到 t 的最大可行流量。

边的流量受限于边的容量。
除了 s 和 t，每个顶点都有相同的流入和流出流量。

Ford-Fulkerson 算法

以下是 Ford-Fulkerson 算法的基本概念

从初始流量 0 开始。
它还包含从源点到汇点的附加通道。
- 使用路径搜索技术（例如：广度优先搜索或深度优先搜索）生成一条扩展路径。
- 计算沿扩展路径可传输的流量。这是路径末端的最小剩余容量。
- 将沿增广路径的流量增加到指定量。
返回最大可能流量。

实施

首先，让我们解释一下理解实现所需的残余图概念。

流网络的残余图表示更多可能的流量。如果残余图有一条从源点到汇点的路径，则可以增加流量。残余图中的每条边都有一个称为残余容量的指示器，其值等于边的初始容量减去其当前流量。残余容量指的是边的当前容量。

现在，让我们深入了解实现的细节。如果残余图中两个顶点之间没有边，则残余容量为零。我们可以将残余图初始化为初始图，因为没有起始流量，并且残余容量的量在开始时等于原始容量。我们可以在残余图上执行 BFS 或 DFS 以发现增广路径。我们可以使用 BFS 来确定是否存在从源点到汇点的路径。BFS 还会生成一个 parent[] 数组。使用 parent[] 数组，我们遍历发现的路径，通过计算沿路径的最小残余容量来确定通过它的可行流量。之后，我们将发现的路径流量包含到总流量中。

关键点在于我们更新残余图中的残余容量。我们从路径中的所有边中减去路径流量，并将其添加到反向边中。我们需要沿反向边提供路径流量，因为我们可能需要沿反向方向发送流量。

示例

让我们举一个例子来说明 C++ 中的 Ford Fulkerson 算法。

文件名：FordFulkerson.cpp

// Program to implement the the Ford-Fulkerson Algorithm 
#include <iostream>
#include <limits.h>
#include <queue>
#include <string.h>
using namespace std;

// Declaring the count of the vertices
#define V 6

/* Returns true if a path exists between source and sink 't' in the residual graph. Additionally, it stores the route in the parent[].*/
bool bfsSearch(int rGraph[V][V], int s, int t, int parent[])
{
	//The initial visited array, which is marked as not listed
	bool visited[V];
	memset(visited, 0, sizeof(visited));

	// Create a queue, enqueue the source vertex, and mark the source
	// vertex as visited
	queue<int> q;
	q.push(s);
	visited[s] = true;
	parent[s] = -1;

	//The logic for the BFS
	while (!q.empty()) {
		int u = q.front();
		q.pop();

		for (int v = 0; v < V; v++) {
			if (visited[v] == false && rGraph[u][v] > 0) {
				// checking for the condition in BFS for any node; we
				//If it is true, then the parent value is set to return true
				if (v == t) {
					parent[v] = u;
					return true;
				}
				q.push(v);
				parent[v] = u;
				visited[v] = true;
			}
		}
	}

	//As the sink node is not reached so, it will return as a false
	return false;
}

// the function for finding the flow in a graph
int fordFulkersonAlgo(int graph[V][V], int s, int t)
{
	int u, v;
     //Create an augmenting path using any path-finding
     // approach, including breadth-first or depth-first search.
    //Determine the quantity of flow that can be s
    //hared down the augmenting path, as well as the 
    //path?s edges' minimal residual capability.
	int rGraph[V]
			[V]; //the capacity of the residual graph
                                         // initialled with 0
				// from i to j (if there is an edge. If
				// rGraph[i][j] is 0, then there is no edge)
	for (u = 0; u < V; u++)
		for (v = 0; v < V; v++)
			rGraph[u][v] = graph[u][v];

	int parent[V]; // the bfs array for storing path
				// store path

	int max_flow = 0; //setting up the initial flow as 0
	//checking if the flow exists is not
	while (bfsSearch(rGraph, s, t, parent)) {
		//The minimum residual capacity can be found, and
		// the path filled by BFS.
                     //Or finding the maximum flow of the path
		int path_flow = INT_MAX;
		for (v = t; v != s; v = parent[v]) {
			u = parent[v];
			path_flow = min(path_flow, rGraph[u][v]);
		}

		//Update and reverse the edges 
		for (v = t; v != s; v = parent[v]) {
			u = parent[v];
			rGraph[u][v] -= path_flow;
			rGraph[v][u] += path_flow;
		}

		// adding up the flow path to the Toal flow
		max_flow += path_flow;
	}

	//The max flow is then returned
	return max_flow;
}

// Main section
int main()
{
	//The initial graph creation
	int graphS[V][V]
		= { { 0, 16, 13, 0, 12, 0 }, { 0, 0, 10, 22, 0, 0 },
			{ 0, 8, 0, 0, 14, 0 }, { 0, 0, 9, 0, 0, 20 },
			{ 0, 0, 0, 7, 0, 4 }, { 0, 0, 0, 1, 0, 0 } };

	cout << "The maximum possible flow is "
		<< fordFulkersonAlgo(graphS, 0, 5);

	return 0;
}

输出

The maximum possible flow is 24

复杂度分析

时间复杂度

时间复杂度为 O(|V| * E^2)，其中 E 是边的数量，V 是顶点的数量。

空间复杂度

空间复杂度为 O(V)，因为我们构建了一个队列。

上述用于 Ford Fulkerson 算法的程序被称为 Edmonds-Karp 算法。Edmonds-Karp 建议在 Ford Fulkerson 解决方案中使用 BFS，因为 BFS 总是选择边数最少的路径。当使用 BFS 时，最坏情况时间复杂度降低到 O(VE^2)。上述实现采用邻接矩阵表示，但当 BFS 需要 O(V^2) 时间时，上述实现需要 O(EV^3)。

Ford Fulkerson 算法的应用

Ford-Fulkerson 算法是计算流网络中最大流最常用的技术。它在不同领域有多种用途。Ford-Fulkerson 方法通常用于以下应用和场景：

网络

Ford-Fulkerson 算法主要用于解决网络流问题。它指定了流网络中可从源点发送到汇点的最大流量。

交通

优化运输和物流网络涉及通过道路、火车或其他运输链接，最大限度地提高产品从供应商到消费者的流量。

电信

该技术可以改善电信网络中的数据流，从而实现多个节点之间的有效通信。

图像分割

在人工智能中，Ford-Fulkerson 方法可以根据强度或颜色等特征将图像分割成片段。

下一主题C++ 中的模板方法模式

C++ Ford Fulkerson 算法

什么是 Ford Fulkerson 算法？

问题

Ford-Fulkerson 算法

实施

示例

Ford Fulkerson 算法的应用

联系信息

关注我们

教程

面试题

在线编译器

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++ Ford Fulkerson 算法

什么是 Ford Fulkerson 算法？

问题

Ford-Fulkerson 算法

实施

示例

Ford Fulkerson 算法的应用

相关帖子

C++ 中的 MakeFile 及其应用

C++ std::common_type T1, T2 ::type 函数

C++ 中的 std::scoped_lock

C++ 与 Object Pascal 的区别

C++ 烟花算法

C++ std::wclog() 函数

C++ Bogosort 算法

C++ 虚函数与纯虚函数的区别

C++ 中的莱尔数实现

C++ 反转单词前缀

订阅 Tpoint Tech

联系信息

关注我们

教程