2

我正在尝试用 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;
}
4

1 回答 1

4

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

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

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();

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

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

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

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

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

花了一些时间来回答您的问题，因为您没有自己追踪问题。如果你给出了上面的例子，我敢打赌你的解决方案会在几分钟内出现。鼓励您在堆栈溢出时提出您的问题 - 但是，大多数成员不愿意通过大量代码自己识别问题。这意味着，高质量的答案通常需要直截了当的问题。（最后一段旨在帮助您将来，但是，可以在不改变问题的情况下减少它）。

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

希望我能帮上忙。

于 2012-01-07T21:52:13.127 回答