最大流图算法

Question

有人知道应该使用哪种算法来找到无向图中的最大流吗？

据我了解，这里的无向网络基本上将图变成了多重图由两个“普通”肋和两个“假”肋连接的顶点，例如在Ford-Fulkerson算法中使用。

但是我应该如何处理多重图的情况呢？

Answer 1

如果您有无向边

     5
* ------ *

，则可以将其转换为两个有向边：

     5
  ------>
*         *
  <------
     5

Ford-Fulkerson 方法可以完美地处理此类图。