如何查找图形扩充路径

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; 
} 

Answer 2

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

Answer 3

这是一个有点很难给你明确的建议不知道底层的数据结构。通常当你处理流程时，你有一个有向图。我会认为这是我的答案。 现在我看到的几个重大问题和一个次要备注：

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

在这里，您将获取您当前所在顶点的邻接列表。但请记住，扩充路径称为扩充（augmenting），因为您可以向前（如果存在剩余容量，因此电流在此边缘上的流量小于边缘的容量）或向后（如果电流流过此边缘边缘更大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访问。但是，您需要提供正确路径的这些顶点的子集。

最后一句话：对于福特Fulkerson增，这可能是一个聪明的想法来计算价值，你可以直接而做BFS的电流路径上增加的流动。这样你就不需要再次访问边缘了。当然，您可以在使用尚未保存的前辈收集路径时进行此操作。

我不会给你一个完整的工作代码示例，因为我认为这是家庭作业，你应该学习的东西，而不是拿完代码。