我使用在Edmonds-Karp算法维基页面找到的伪代码实现了该算法:http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm。它运行得很好,但是算法的输出只是最大流值(最小割值),我需要这个割包含的边的列表。
我尝试改变算法,但没有成功,你们能帮忙吗?
谢谢。
我尝试改变算法,但没有成功,你们能帮忙吗?
谢谢。
为了找到S顶点,请从源顶点开始进行BFS(或DFS)搜索,仅跟随某些剩余流量容量的边。 (换句话说,非饱和边)。 这些定义上不能在最小割中。
要找到T顶点,请从汇点顶点开始执行BFS(或DFS)搜索,只连接尚未添加到S集合中的顶点。 它们可以具有剩余流量,也可能完全饱和,这并不重要。 因为您正在从汇点执行BFS,所以如果图形是定向的,则需要确保按相反方向沿着边指向传递。 注意:仅在T集合中包括可以从汇点到达的顶点很重要,否则您将在最小割中包含不属于那里的边缘。 (这是让我困扰了很长时间的原因。)
一旦您拥有这两组顶点,就可以迭代整个图的所有边。 任何具有在S中的源节点和在T中的目标节点的边缘都是最小割的一部分。 但是要注意,这只是许多可能的最小割之一。 在图中找到所有可能的S-T最小割需要更多时间。
如果你已经知道了最大流量,那么最小割是(S,T),其中S是从源节点在残余网络中可到达的顶点集,而T是补集。连接S中的一个顶点和T中的一个顶点的边属于割。