相关疑难解决方法(0)

我正在尝试使用Ford-Fulkerson算法解决图的最大流问题.该算法仅用有向图描述.当图表无向时怎么办？

我模仿无向图的方法是在一对顶点之间使用两个有向边.令我困惑的是:这些边缘中的每一个是否应该有剩余边缘,或者是剩余边缘的"相对"有向边缘？

我假设了最后一个,但我的算法似乎进入了无限循环.我希望你们中的任何人能给我一些帮助.以下是我自己的实现.我正在使用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 …