algorithm - 网络流算法的适当图形表示

Question

实现Ford-Fulkerson时或 Dinitz最大网络流量的算法有两个需要在图上执行的操作:

• 遍历给定顶点的所有邻居
• 找到给定边的反向边(当沿着增广路径添加流时，图形修改需要这样做)。

理想情况下，第一个操作与邻居的数量成线性关系，第二个操作应该是常数。此外，图形表示所需的内存应该与边数成线性关系(请注意，对于最大网络流算法的大多数实际应用，我已经看到边数大约是顶点数的线性倍数)。仅当满足上述约束条件时，对这两种算法的复杂性的所有估计才会成立。

问题是没有一个经典的图形表示能够满足上述要求:

邻接矩阵

使用邻接矩阵，可以在常数时间内找到给定边的反向边。然而，遍历所有邻居与所有顶点的数量成线性关系，并且所需的内存与顶点数量成二次方。

边列表

使用这种表示，遍历所有邻居将不会与邻居的数量成线性关系，并且找到给定边的反向边也不是恒定的。

邻居列表

使用这种表示，我们可以在线性时间内遍历所有邻居，而且所需的内存与边数成线性关系。尽管如此，找到给定边的反向边将与目标顶点的邻居数量成线性关系。

通过稍微修改此表示，我们可以改进这一点 - 如果我们保留邻居的一些二叉搜索树而不是邻居列表，我们可以找到具有对数复杂度的反向边。甚至更好——如果我们使用 HashMap 而不是二叉搜索树，我们将拥有恒定的摊销复杂性。这种表示仍然感觉不对 - 虽然仍然是线性的，但 HashMap 有一些内存开销。此外，它仅具有摊销的恒定复杂性，因此某些操作实际上可能更慢。

问题

所以我的问题是:什么样的图形表示适合实现最大网络流量算法？

Answer 1

我会将 Ivaylo 的表示描述为“边缘连续”。还有一个“端点连续”表示，我相信从一个极其不科学的样本中可以得到更广泛的使用。我在不同的时间都实现过。

如果没有硬数据，我的假设是端点连续表示对于通常可疑的网络流算法比边缘连续表示更好，因为边缘连续表示每次扫描弧时都会产生随机访问，而端点-连续的，每次流被推到弧上(大概​​是在扫描弧之前)。这种表示的明显优势是它支持非对称图(与网络流不太相关)。这种表示的明显缺点是更改图形的拓扑要慢得多。

表示由两个数组组成。 first，包含 n+1 个元素，存储具有指定尾部的第一个弧的索引。额外的条目是弧的总数 m，因此尾部为 v 的弧的索引是 first[v] 包含到 first[v+1] 不包含。在 Ivaylo 的图表上，

[0] = 0->1, [1] = 0->2,
[2] = 1->0, [3] = 1->2, [4] = 1->3,
[5] = 2->0, [6] = 2->1, [7] = 2->3, [8] = 2->4,
[9] = 3->1, [10] = 3->2, [11] = 3->5,
[12] = 4->2, [13] = 4->5,
[14] = 5->3, [15] = 5->4,

数组first是

0, 2, 5, 9, 12, 14, 16.

弧本身存储在以下结构类型的 m 元素数组中。

struct Arc {
    int head;
    int capacity;
    int symmetric;
};

symmetric 是对称弧的索引。