For循環遞歸函數在遞歸結束後繼續

我在C++中的圖上實現深度優先搜索。給定一個起始頂點，該算法應該執行DFS，直到找到一個目標節點（即一個goal設置爲true的節點），並返回所採用的路徑。我試圖遞歸地做到這一點，這是我的代碼：For循環遞歸函數在遞歸結束後繼續

vector<char>* dfs(graph g, node* s){ 

    static vector<char> path; 
    s->set_visited(); 
    path.push_back(s->get_tag()); //Adds node to path 

    if(s->is_goal()){ 
     g.set_all_visited(); 
    } 

    else{ 
     for(int i=0; i<(s->get_no_edges()); i++){ 
      if(!(s->get_edge(i)->get_dest()->is_visited())) //If it is unvisited, apply recursion 
       dfs(g, s->get_edge(i)->get_dest()); 
     } 
    } 

    return &path; 
}

據我所知，所產生的路徑將只列出他們由DFS訪問的順序節點，從不是一個實際的路徑開始到目標節點。

問題在於，即使在找到目標節點之後，函數仍繼續打印節點。爲了避免這種情況，我將圖g中的所有節點設置爲使用set_all_visited()訪問，並在繼續前檢查了else部分中是否訪問了節點，但這似乎不起作用。當我執行幹運行時，即使在找到目標節點之後，該功能仍然訪問for循環中節點的所有邊緣，並且我不知道如何阻止該情況發生。

來源

2017-04-05 Stefania Damato

也許它與按值傳遞'g'有關。嘗試通過引用傳遞它。將所有節點標記爲已訪問的'g'與其他遞歸調用可用的'g'不同。 – IVlad

https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ 特別是在這種情況下，你似乎確信它停留在for循環 - 因此'我<(s-> get_no_edges（））是真的。所以，在調試器（或者使用'窮人'調試器'cout'）看看'i'和's-> get_no_edges（）'，然後看看爲什麼這個條件仍然是真的。 – slim

@IVlad我試了一下，它似乎現在工作！這樣愚蠢的錯誤。謝謝！ –

您按值傳遞g而不是引用。這意味着無論何時您找到一個目標節點並從遞歸調用返回時，該實例g仍將其節點設置爲未訪問。這就是重複發生的原因。

來源

2017-04-05 16:23:02

我知道你的主要問題是回答，我還是會給一些建議：

1）不要使用靜態載體，你不能重用功能。你可以創建一個你期待路徑的向量並傳遞指向該向量的指針。

2）爲了確保路徑中沒有所有訪問過的節點，可以從dfs函數返回一個bool來表示是否有到目的地的路徑。您也可以避免以這種方式傳遞圖形對象。

這些變化你的代碼將變爲：

bool dfs(node* s, vector<char>* path){ 

    s->set_visited(); 

    if(s->is_goal()){ 
     path.push_back(s->get_tag()); 
     return true; 
    } 

    else{ 
     for(int i=0; i<(s->get_no_edges()); i++){ 
      if(!(s->get_edge(i)->get_dest()->is_visited())) //If it is unvisited, apply recursion 
       if(dfs(s->get_edge(i)->get_dest(), path)) { 
        path.push_back(s->get_tag()); 
        return true; 
       } 
     } 
    } 

    return false; 
}

這將返回反向路徑，從目的到源路徑，即，存在的std ::相反。

如果你做了一個BFS，你會得到最短路徑而不是一些隨機路徑，假設邊的權重相同。

來源

2017-04-05 16:54:57

太棒了！改變它像你說的，歡呼。 –

For循環遞歸函數在遞歸結束後繼續

回答

相關問題