我知道一个算法可以找到平面图中的最小割。
作为 O(NlogN)
您创建一个对偶图，其中每个顶点对应于原始图的分面，边对应于连接两个分面的最小边。
然后您使用 Dijkstra 找到该图中的最小路径。
这样就可以找到最小割并计算流量值。
但是我怎样才能找到提供这个流值的任何原始图边集呢？
最佳答案
您所描述的算法仅适用于无向图(Reif 算法)。 Hassin 和 Johnson 展示了如何扩展它来计算最大流量。最近表明，这些算法可以在 O(n loglog n) 时间内实现。请参见 G. F. Italiano、Y. Nussbaum、P. Sankowski 和 C. Wulff-Nilsen 改进的无向平面图中最小割和最大流算法。在过程中。第 43 届 ACM 计算理论研讨会 (STOC)，圣何塞，2011 年。
在有向平面图中，最快的已知算法在 O(n log n) 中运行，请参阅 http://web.engr.oregonstate.edu/~glencora/papers/other/Borradaile08-thesis-dissertation.pdf或者 http://compgeom.cs.uiuc.edu/~jeffe/pubs/parshort.html
关于algorithm - 如何在平面图中找到最大流？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10667751/