如何查找圖形擴充路徑

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的電流路徑上增加的流動。這樣你就不需要再次訪問邊緣了。當然，您可以在使用尚未保存的前輩收集路徑時進行此操作。

我不會給你一個完整的工作代碼示例，因爲我認爲這是家庭作業，你應該學習的東西，而不是拿完代碼。