java - 难以理解和实现 Ford Fulkerson 算法

Question

我正在尝试用 Java 实现 Ford Fulkerson 算法。到目前为止，我有一个包含节点和边的图。节点包含一个 ID 字符串和一个边的邻接列表。边包含容量和它通向的节点。

我正在尝试理解维基百科页面上的伪代码以及如何实现它(我使用的是 Java)。这是我目前的理解:

1. 首先我将图中所有边的流设置为零。(什么是表示流的好方法？直接在我的图的边中作为变量？)

2. 第二步是创建残差图，这是一个边具有残差容量的网络:容量 - 流量(“正常图”中相应边的流量)。然后你使用这个残差图找到从源到汇的路径，并找到沿着这条路径的最小容量。 (这是事情变得非常棘手的地方，我应该为残差图创建一个全新的图还是应该在原始图中以某种方式表示它？最好的方法是什么？)

重复第 2 步，直到找不到路径，但每次找到您都执行第 3 步和第 4 步:

1. 对于沿路径的每条边，您添加在步骤 2 中找到的最小值。

2. 对于路径相反方向的每条边，您减去在步骤 2 中找到的最小值。

第 3 步和第 4 步让我感到困惑，因为我觉得在一个方向上加法和在相反方向上减法是一回事。这些加减法是在graph right 做的，不是residual graph？

非常感谢您的帮助，几个小时以来我一直在努力思考这个问题，但我似乎无法理解它。

Answer 1

您可能应该首先使用密集图来实现它。这样，您可以假设每对不同顶点之间的每个方向都有一条边。您可以将边上的函数表示为 |V| x |V|矩阵。特别是容量和流量的声明非常简单:

int[][] cap = new int[numverts][numverts];
int[][] flow = new int[numverts][numverts];

一个有用的技巧是表示 k 的流沿边单位 vw作为 a 的流量来自 v至 w和 -a 的流量来自 w至 v .这样，您就不必担心增广路径的每条边是向前插入更多流量还是向后插入更少流量。如果这样做，您可以计算沿 vw 的剩余容量。通过简单地 cap[v][w] - flow[v][w] .

通过这种表示，在密集图中寻找增广路径变成了广度优先搜索，其中有一条边来自 v。至 w什么时候 cap[v][w] > flow[v][w] .这是相当直接实现的。

由于您使用的是 java，因此您应该注意它对每个对象的开销。您描述的 Edge 结构不仅包含两个整数(或指针)和两个 double ，还包含 GC 信息、类指针和监视器等内容。这是几十个额外的字节，很容易使对象的大小增加一倍或三倍。

当您开始使用稀疏图来使代码工作时，静态稀疏图的更好表示如下:

int[] from = new int[numverts+1];
int[] to = new int[numedges];

按“从”顶点对边进行排序。 i from 的第一个条目array 是第一条边的索引，其“from”顶点是 i th 顶点或以后。最后有一个额外的条目，您应该将其设置为 numedges ;当您想遍历离开给定顶点的所有边时，它会派上用场。

因为你在做流，你也想存储向后的边缘，所以有一个

int[] rev = new int[numedges];

存储每条边反转的边索引。现在你可以表示任意函数，比如 cap和 flow ，像这样的边缘:

int[] cap = new int[numedges];
int[] flow = new int[numedges];

那么是否将这些属性存储在Edge中结构没有实际意义，因为 Edge结构消失了。