C#，计算图最大流量的福特-富尔克森（Ford Fulkerson）算法与源程序

Ford-Fulkerson算法（FFA）是一种贪婪算法，用于计算流网络中的最大流量。 它被称为“方法”而不是“算法”，因为在残差图中找到增广路径的方法没有完全指定，或者在具有不同运行时间的若干实现中指定。 它由L. R. Ford，Jr。和D. R. Fulkerson于1956年出版。 名称“Ford-Fulkerson”通常也用于Edmonds-Karp算法，该算法是Ford-Fulkerson方法的完全定义的实现。

 Lester Randolph Ford, 1947-1948 MAA President

 

算法背后的想法如下：只要存在从源（起始节点）到接收器（端节点）的路径，在路径中的所有边缘上具有可用容量，我们就沿着其中一个路径发送流。 然后我们找到另一条路径，依此类推。 具有可用容量的路径称为扩充路径。

通过将流量增加路径添加到已建立的流量，当不再能够找到流量增加路径时，将达到最大流量。但是，无法确定是否会达到这种情况，因此可以保证的最佳方案是，如果算法终止，答案将是正确的。在算法永远运行的情况下，流可能甚至不会收敛到最大流量。但是，这种情况只发生在不合理的流量值。当容量为整数时，Ford-Fulkerson的运行时间受O（E f）的限制（参见大O表示法），其中E是边和f是最大流量。这是因为每个扩充路径都可以在O（E））时间内找到并且将流量增加至少1 的整数量，其上限f 。
 

 

给出一个图，该图表示每个边都有容量的流网络。同时在图中给定两个顶点源“s”和汇“t”，在以下约束条件下，找到从s到t的最大可能流：

a） 边上的流量不会超过边的给定容量。

b） 除了s和t之外，每个顶点的传入流都等于传出流。

如何实现上述简单算法？

让我们首先定义残差图的概念，这是理解实现所需的。

流量网络的残差图是表示其他可能流量的图。若在残差图中有一条从源到汇的路径，那个么就可以添加流。剩余图的每条边都有一个称为剩余容量的值，该值等于边的原始容量减去当前流量。剩余容量基本上是边缘的当前容量。

现在让我们谈谈实现细节。如果残差图的两个顶点之间没有边，则残差容量为0。我们可以将残差图初始化为原始图，因为没有初始流，并且初始残差容量等于原始容量。为了找到增广路径，我们可以对残差图进行BFS或DFS。我们在下面的实现中使用了BFS。使用BFS，我们可以发现是否存在从源到汇的路径。BFS还构建父[]数组。使用父[]数组，我们遍历找到的路径，并通过查找路径上的最小剩余容量来查找通过该路径的可能流量。我们稍后将找到的路径流添加到总体流中。

重要的是，我们需要更新残差图中的残差容量。我们从沿路径的所有边上减去路径流，然后沿反向边添加路径流。我们需要沿反向边添加路径流，因为以后可能需要沿反向发送流（例如，请参见以下链接）。

参考:

C#，图（Graph）的数据结构设计与源代码https://blog.csdn.net/beijinghorn/article/details/125133711?spm=1001.2014.3001.5501

源代码(POWER BY TRUFFER)：

using System;
using System.Collections;
using System.Collections.Generic;
 
namespace Legalsoft.Truffer.Algorithm
{
	public partial class Graph
	{
		private static bool BFS_Ford_Fulkerson(int[,] graph, int s, int t, int[] parent)
		{
			int N = graph.GetLength(0);
 
			bool[] visited = new bool[N];
			for (int i = 0; i < N; i++)
			{
				visited[i] = false;
			}
 
			List<int> queue = new List<int>();
			queue.Add(s);
			visited[s] = true;
			parent[s] = -1;
 
			while (queue.Count != 0)
			{
				int u = queue[0];
				queue.RemoveAt(0);
				for (int v = 0; v < N; v++)
				{
					if (visited[v] == false && graph[u, v] > 0)
					{
						if (v == t)
						{
							parent[v] = u;
							return true;
						}
						queue.Add(v);
						parent[v] = u;
						visited[v] = true;
					}
				}
			}
 
			return false;
		}
 
        public int Ford_Fulkerson(int s, int t)
		{
			int N = Node_Number;
			int[,] rGraph = new int[N, N];
 
			int u, v;
			for (u = 0; u < N; u++)
			{
				for (v = 0; v < N; v++)
				{
					rGraph[u, v] = Matrix[u, v];
				}
			}
			int[] parent = new int[N];
			int max_flow = 0;
 
			while (BFS_Ford_Fulkerson(rGraph, s, t, parent))
			{
				int path_flow = int.MaxValue;
				for (v = t; v != s; v = parent[v])
				{
					u = parent[v];
					path_flow = Math.Min(path_flow, rGraph[u, v]);
				}
 
				for (v = t; v != s; v = parent[v])
				{
					u = parent[v];
					rGraph[u, v] -= path_flow;
					rGraph[v, u] += path_flow;
				}
 
				max_flow += path_flow;
			}
 
			return max_flow;
		}
	}
 
	public static partial class GraphDrives
	{
		public static string MaxFlow()
		{
			int[,] graph = new int[,] {
				{ 0, 16, 13, 0, 0, 0 },
				{ 0, 0, 10, 12, 0, 0 },
				{ 0, 4, 0, 0, 14, 0 },
				{ 0, 0, 9, 0, 0, 20 },
				{ 0, 0, 0, 7, 0, 4 },
				{ 0, 0, 0, 0, 0, 0 }
			};
 
			Graph g = new Graph(graph);
			g.AdjacencyMatrix();
			return ("The maximum possible flow is " + g.Ford_Fulkerson(0, 5));
		}
	}
}