c++ - 如何找到图形增广路径

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

阅读here .基本上使用 Breadth-first_search .

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

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