如何找到图增广路径

Question

我正在尝试实现 Ford-Fulkerson 算法 来计算流网络中的最大流量。

该算法的一个步骤是找到一条从起始节点到结束节点（也称为汇点）且所有边上都具有可用容量的路径。

您能否建议一种简单易懂的方法来找到增强路径？

更新 #1：

我的 BFS 函数：

template <class T>
vector<Vertex<T> *> Graph<T>::bfs(T source) const {
    vector<Vertex<T> *> path;
    queue<Vertex<T> *> q;
    Vertex<T> * v = getVertex(source);
    q.push(v);
    v->visited = true;
    while (!q.empty()) {
        Vertex<T> *v1 = q.front();
        q.pop();
        path.push_back(v1);
        typename vector<Edge<T> >::iterator it = v1->adj.begin();
        typename vector<Edge<T> >::iterator ite = v1->adj.end();
        for (; it!=ite; it++) {
            Vertex<T> *d = it->dest;
            if (d->visited == false) {
                d->visited = true;
                q.push(d);
            }
        }
    }

    return path;
}

它是错误/不完整的，因为它返回了错误的结果。我想我忘记了什么。

Answer 1

请阅读此处。基本上使用Breadth-first_search。

编辑： path.push_back(v1); 位于错误的位置。您将把图形的所有顶点添加到路径中。正确的方法是为每个节点存储前驱节点。这样你就可以恢复找到的路径。您还可以在到达接收器时中断 while 子句。

if (d->visited == false) {
    d->visited = true;
    q.push(d);
    predecessor[d] = v1;
}

Answer 2

在不了解底层数据结构的情况下给你明确的建议有点困难。通常当你处理流时，你会有一个有向图。我将假设这是我的答案。
现在我看到了一些主要问题和一个小评论：

template <class T>
vector<Vertex<T> *> Graph<T>::bfs(T source) const {
    vector<Vertex<T> *> path;   

在这种情况下，列表可能是更好的选择，因为向量仅摊销恒定的插入和删除时间，而列表确实是恒定的。 （假设您指的是 STL 容器）- 这是次要评论；）

    queue<Vertex<T> *> q;

对于 BFS，您有两个选择：要么保存所有路径，要么在访问每个顶点后保存其前趋。您只需保存必须访问的顶点即可。这样，我不知道一旦到达水槽，您将如何重建完整的路径。

    Vertex<T> * v = getVertex(source);
    q.push(v);
    v->visited = true;

初始化对我来说似乎很好。

    while (!q.empty()) {
        Vertex<T> *v1 = q.front();
        q.pop();
        path.push_back(v1);
        typename vector<Edge<T> >::iterator it = v1->adj.begin();
        typename vector<Edge<T> >::iterator ite = v1->adj.end();

在这里，您获取当前所在顶点的邻接列表。但请记住，增广路径之所以称为增广，是因为您可以向前（如果还有剩余容量，因此流过该边的电流小于该边的容量）或向后（如果流过该边的电流）遍历一条边。边缘大于 0）。您只需获取图中前进的所有边并访问它们即可。这是“正常”BFS，而不是适应最大流问题中使用的不同图结构的 BFS。

（为了完整性：你可以将你的网络与当前流结合起来，并从中创建一个新图（我知道这个是辅助网络），它准确地代表了这个结构。在这种情况下，你的 BFS 会工作得很好。如果你正在做现在，我想看看辅助网络的例程计算）。

        for (; it!=ite; it++) {
            Vertex<T> *d = it->dest;
            if (d->visited == false) {
                d->visited = true;
                q.push(d);
            }
        }
    }

除了我已经提到的几点之外，这部分对我来说看起来不错。因此 - 保存前趋，检查路径是否对最大流量有帮助（有剩余容量）并检查向后弧。

    return path;

再看看您在路径变量中收集的内容。实际上，您按照访问顺序将 BFS 访问的所有顶点保存在其中。但是，您需要这些顶点的子集来提供正确的路径。

最后评论：对于 Ford-Fulkerson，在执行 BFS 时直接计算可以在当前路径上增加流量的值可能是一个聪明的主意。这样您就不需要再次访问边缘。当然，您可以在使用尚未保存的前辈收集路径的同时执行此操作。

我不会给您完整的工作代码示例，因为我认为这是家庭作业，您应该学习一些东西而不是获得完成的代码。

Answer 3

看一下源代码：这里是 http://aduni.org/courses /algorithms/courseware/handouts/Reciation_09.html