使用 Ford Fulkerson 算法找到边缘？

Question

我正在尝试用 C++ 实现福特富尔克森算法。

但是，我的 find_edge 函数遇到了问题。当我在 my_alg 中调用此函数时，它会选择正确的边缘，然后在 my_alg 中增加流量。它选择右边缘并增加其流量 (flow)，但是当我再次调用 find_edge 函数时，流量并未按应有的方式增加。

这导致我的算法陷入无限循环。可能我对指针做错了什么。你可以在下面看到我的代码。

//An object of this class represents an edge in the graph.
class Edge
{
private:
    //Node *prev;

public:
    int flow;

    Edge(Node *firstNode, Node *secNode, unsigned inCost) {
        orgNode = firstNode;
        dstNode = secNode;
        bridge_capacity = inCost;
    }

    Edge() {
        flow=0;
    }
};

//An object of this class holds a vertex of the graph
class Node
{
public:
    Node *prev;

    vector<Edge>& getAdjNodeList() {
        return adjNodeList;
    }
};

Edge *find_edge(Graph *g,Node *from,Node *to) {
    vector<Edge> b=from->getAdjNodeList();
    for(int i=0;i<b.size();i++) {
        if(b[i].getDstNode()==to)
            return (&b[i]);
    }
    return NULL;
}

int my_alg(Graph *as,Node *source,Node *sink){
    Edge *find_edge();

    int max_flow=0;

    while(bfs(as,source,sink)) {
        Node *b=as->nodeList[num_isl];
        int inc=100000000;
        while(b->prev!=NULL) {
            Edge *bok=find_edge(as,b->prev,b);
            inc=min(inc,bok->get_bridge_capacity()-bok->flow);
            b=b->prev;
        }

        b=as->nodeList[num_isl];

        while(b->prev!=NULL){
            Edge *bok = find_edge(as,b->prev,b);
            bok->flow += inc;       // This is the place the flow is incremented
            bout << bok->flow;      // Here, everything is alright.
            bok = find_edge(as,b->prev,b);
            cout << bok->flow;      // However, this is is not the correct result.
        }
        max_flow+=inc;
    }
    return max_flow;
}

Answer 1

我更彻底地查看了您的代码。为了帮助您将来自己跟踪问题，我将向您展示一个查找错误的示例过程。

如果您确实无法通过查看代码找到问题，您可能需要删除所有混淆您对问题的看法的内容。简化后的代码可能如下所示：

class Edge {
public:
    int flow;
};    

class Node {
private:
    vector<Edge> adjNodeList; // list of outgoing edges for this vertex

public:
    vector<Edge> & getAdjNodeList() {
        return adjNodeList;
    }

    void addAdjNode(Node* newAdj) {
        adjNodeList.push_back(Edge(newAdj));
    }
 };    


int main() {
    Node *node1 = new Node();
    Node *node2 = new Node();
    node1->addAdjNode(node2);

    vector<Edge> t = node1->getAdjNodeList();
    vector<Edge> f = node1->getAdjNodeList();
    t[0].flow = 11;

    cout << t[0] << endl;
    cout << f[0] << endl;
}

如果您运行此代码，您会注意到 t[0] 和 f[0] 不同。由于我刚刚复制了您代码的关键元素，因此原因应该仍然相同。

这里发生了什么？当调用

vector<Edge> t = node1->getAdjNodeList();

邻接列表时，通过引用返回，这应该给您留下对原始列表的引用 - 您应该能够更改它的元素，不是吗？但是，当将此引用分配给新分配的向量 t 时，会调用隐式复制构造函数，因此 t 将包含向量的副本（！），而您想要保存一个参考。

要解决这个问题，您可以执行以下操作：

vector<Edge> & t = node1->getAdjNodeList();

保存引用并且不创建新对象。

我只能假设为什么在函数调用之间指针恰好相同：该对象可能每次都被复制到同一个位置。此外，请注意，您增加了不再存在的对象的值 - 副本在 find_edge 调用结束时被删除。

由于您没有亲自找到问题所在，所以花了一些时间才回答您的问题。如果您给出了上面的示例，我敢打赌您的解决方案将在几分钟之内出现。我们鼓励您在堆栈溢出时提出您的问题 - 然而，大多数成员不愿意通过大量代码来自己识别问题。这意味着高质量的答案通常需要直接切中要点的问题。 （最后一段是为了将来为您提供帮助，但是，可以在不改变问题的情况下减少它）。

除此之外，我强烈建议您不要像现在这样使用您的物品。通过将所有内容作为引用传递并在对象外部进行所有更改，您基本上绕过了使面向对象编程变得如此强大的封装。例如，如果您只是将另一个函数 increaseFlow(Edge* to, intincrement) 添加到您的 Node ，那会更明智（并且不会给您带来问题） > 并完成了对象内的所有操作。

希望我能帮忙。