最大流 - 福特-福尔克森：无向图

Question

我正在尝试用福特-福尔克森算法解决图的最大流问题。这个算法只是在有向图上描述的。那么，当图是无向的时候该怎么处理呢？

为了模拟无向图，我在一对顶点之间使用了两条有向边。让我困惑的是：这两条边每条都应该有一条残余边吗？还是说“相反”的有向边就是残余边呢？

我假设是后者，但我的算法似乎陷入了无限循环。我希望你们能给我一些帮助。下面是我自己的实现代码。我在查找时使用了深度优先搜索（DFS）。

import sys
import fileinput

class Vertex(object):
    def __init__(self, name):
        self.name = name
        self.edges = []

    def find(self, sink, path):
        if(self == sink):
            return path
        for edge in self.edges:
            residual = edge.capacity - edge.flow
            if(residual > 0 or edge.inf):
                if(edge not in path and edge.oppositeEdge not in path):
                    toVertex = edge.toVertex
                    path.append(edge)
                    result = toVertex.find(sink, path)
                    if result != None:
                        return result

class Edge(object):
    def __init__(self, fromVertex, toVertex, capacity):
        self.fromVertex = fromVertex
        self.toVertex = toVertex
        self.capacity = capacity
        self.flow = 0
        self.inf = False
        if(capacity == -1):
            self.inf = True
    def __repr__(self):
        return self.fromVertex.name.strip() + " - " + self.toVertex.name.strip()

def buildGraph(vertices, edges):
    for edge in edges:
        sourceVertex = vertices[int(edge[0])]
        sinkVertex = vertices[int(edge[1])]
        capacity = int(edge[2])
        edge1 = Edge(sourceVertex, sinkVertex, capacity)
        edge2 = Edge(sinkVertex, sourceVertex, capacity)
        sourceVertex.edges.append(edge1)
        sinkVertex.edges.append(edge2)
        edge1.oppositeEdge = edge2
        edge2.oppositeEdge = edge1

def maxFlow(source, sink):
    path = source.find(sink, [])
    while path != None:
        minCap = sys.maxint
        for e in path:
            if(e.capacity < minCap and not e.inf):
                minCap = e.capacity

        for edge in path:
            edge.flow += minCap
            edge.oppositeEdge.flow -= minCap
        path = source.find(sink, [])

    return sum(e.flow for e in source.edges)

vertices, edges = parse()
buildGraph(vertices, edges)
source = vertices[0]
sink = vertices[len(vertices)-1]
maxFlow = maxFlow(source, sink)

Answer 1

你用两条反向边的方式是可行的。如果你的边是 a->b（容量是10，我们通过它发送了7），那么我们就要引入一条新的剩余边（从 b 到 a，它的剩余容量是17，而从 a 到 b 的剩余边还有3的容量）。

原来的反向边（从 b 到 a）可以保持不变，或者把新引入的剩余边和原来的反向边合并成一条边。

我觉得把剩余容量加到原来的反向边上可能会简单一些，但我不太确定。