我有一个有向图，边上有流量，我想通过删除所有循环流来简化它。这可以通过在任何给定循环中找到沿每条边的流量的最小值，并将循环中每条边的流量减少该最小量，删除流量为零的边来完成。删除所有循环流后，该图将是非循环的。
例如，如果我有一个图，其中顶点 A、B 和 C 的流为 1 从 A→B，2 从 B→C 和 3 从 C→A，那么我可以重写它而不从 A→B 流，1个来自B→C，2个来自C→A。图中的边数从 3 条减少到 2 条，生成的图是无环的。
哪种算法(如果有的话)可以解决这个问题？
最佳答案
您可能会发现使用流分解定理(参见this discussion of max-flow 的§6.2)很有用，它表示任何流都可以分解为一组流路径和流循环。此外，图中至多可以有m个总流路和循环。这意味着消除流动循环的一种简单算法是找到图中的所有流动路径，然后删除图中所有剩余的流动，因为它必须对应于流动循环。
要查找流动路径或循环，您可以从源节点使用简单的深度优先搜索。从源节点开始，按照您的喜好继续沿边移动，直到您到达终端节点或访问您之前访问过的节点。如果您到达了终端节点，那么您选择的路径就是一条简单的流程路径。如果你两次遇到某个节点，你就找到了一个流动循环(由你刚刚找到的循环形成)。如果您随后从图中删除流路/循环并重复，您将最终检测到所有流路和循环。当没有离开源代码的流动边缘时，您就知道您已经完成了。如果每次找到一条流路时，您都会记录其所有边上的总流量，则可以通过重复此操作直到没有流路剩余，清除网络中的流，然后重新添加流路来消除循环流。
由于每个DFS耗时O(m + n)，最多有O(m)条流路，所以这一步的总运行时间为O(m2 + mn)，即图形大小的多项式。
希望这对您有所帮助!
关于algorithm - 从图中消除循环流，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5370052/