用於遞歸深度優先搜索以存儲路徑的額外空間

我使用深度優先搜索來識別有向加權圖中的路徑，同時重新訪問屬於一個循環的節點，並根據總行進距離設置截斷條件，或者從源節點停止。用於遞歸深度優先搜索以存儲路徑的額外空間

據我瞭解，遞歸明確的堆疊結構不需要深度優先搜索，所以我在想，如果我可以進一步通過某種方式做不明確的堆棧下方簡化我的代碼：

public class DFSonWeightedDirectedGraph { 

    private static final String START = "A"; 
    private static final String END = "E"; 
    private int pathLength = 0; 
    private int stops = 0; 

    public static void main(String[] args) { 
     //this is a directed weighted graph 
     WeightedDirectedGraph graph = new WeightedDirectedGraph(); 
     graph.addEdge("A", "B", 15); 
     graph.addEdge("A", "D", 15); 
     graph.addEdge("A", "E", 27); 
     //(...) more edges added 


     Stack<String> visited = new Stack<String>();   
     visited.push(START); 

     new DFSonWeightedDirectedGraph().depthFirst(graph, visited); 
    } 

    private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) { 

     Collection<Map.Entry<String, Integer>> tree_of_children 
      = graph.get_tree_of_children(visited.peek()); 

     for (Map.Entry<String, Integer> child : tree_of_children) { 


      if(pathLength + child.getValue()>= 20){ 
       continue; 
      }  


      visited.push(child.getKey()); 
      pathLength += child.getValue(); 
      stops += 1;   

      if (child.getKey().equals(END)) { 
       printPath(visited); 
      } 

      depthFirst(graph, visited); 
      visited.pop(); 
      pathLength -= child.getValue(); 
      stops -= 1; 
     } 
    } 

    private void printPath(Stack<String> visited) { 
     for (String node : visited) { 
      System.out.print(node); 
      System.out.print(" "); 
     } 
     System.out.println("[path length: "+pathLength + 
       " stops made: " + stops +"]"); 
    } 
}

然而，沒有明確堆棧結構的其他遞歸實現通常會考慮已訪問節點，將它們着色爲白色，灰色或黑色。那麼，在我的情況下，允許重新訪問，並且需要記錄路徑，是絕對需要的顯式堆棧？感謝您提供更簡單替代方案的任何建議。

來源

2010-01-09 denchr

如果您必須保存路徑，您需要一個數據結構。你的堆棧是好的;你可以用另一個數據結構替換它，但不能擺脫它。

如果可以直接打印路徑（而不記錄它），則不需要堆棧。然後，您可以更改方法簽名以獲取圖形和實際節點（也可能是實際路徑長度和「停止」）。

來源

2010-01-09 11:15:50 Arne

謝謝，這很有意義。所以基本上推理是，如果需要存儲器來保存路徑以供進一步使用，那麼無論實現多餘空間都是必需的 – denchr 2010-01-09 13:37:40

-1

編輯：這個答案是完全偏離主題，並張貼錯誤的解釋問題。

您的DFS實施有幾個問題。是的，它以深度優先的方式訪問所有節點，並且最終設法找到START和END之間的路徑，但它不會嘗試檢查已訪問的節點並且沒有真正原因保留堆棧。你不會陷入循環中的無限遞歸的唯一原因是因爲你限制了最大路徑長度，並且對於所有頂點對之間有多條不同路徑的圖，你仍然需要很長時間。

您正在使用堆棧的唯一方法是通過要訪問的節點旁邊的dfs功能。您可以簡單地擺脫堆棧並直接傳遞節點。

所以，相反的

private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) { 
    ... 
    visited.push(child); 
    ... 
    depthFirst(graph, visited);

你可以簡單地寫爲

private void depthFirst(WeightedDirectedGraph graph, String node) { 
    ... 
    //visited.push(child); <-- No longer needed 
    ... 
    depthFirst(graph, child);

您使用的是您有一個名爲「訪問」，但你不使用的數據結構（棧）存儲/標記哪些節點已經被訪問以避免重新訪問。

您可以修改您現有的代碼，使其具有一個名爲visited的Set（使其成爲全局/類變量，或像遞交調用一樣將其傳遞給您的堆棧），在那裏保留已訪問過的所有節點，並只調用depthFirst（）在那些不在那個Set中的節點上。

這應該使你的代碼看起來像這樣

private void depthFirst(WeightedDirectedGraph graph, String node, Set<String> visited) { 
    visited.add(node); // mark current node as visited 
    ... 
    //visited.push(child); <-- No longer needed 
    ... 
    if (!visited.contains(child)){ // don't visit nodes we have worked on already 
     depthFirst(graph, child); 
    }

到目前爲止，我的答案一直試圖修改代碼，使其工作。但在我看來，您需要更好地瞭解DFS的實際內容以及它的實際工作原理。閱讀任何好的算法/圖論方面的書的相關章節將對你有很大的幫助。我會推薦CLRS（它在簡單圖遍歷方面有一個很好的篇章），但是任何好的書都應該這樣做。簡單而正確的遞歸DFS可以使用數組以更簡單的方式實現，而不必求助於堆棧或集合。

編輯：我沒有提到如何在更換堆棧後檢索路徑。這可以通過使用存儲每個節點的父節點的Map來輕鬆完成。可以使用遞歸printPath（String node）函數獲取路徑（如果有的話），該函數將打印傳遞給它的節點並再次在其父節點上調用自身。

來源

2010-01-09 12:58:42 MAK

在我的帖子中提到了我使用這種方法的問題上下文。我做*不*要求跟蹤訪問節點。 – denchr 2010-01-09 13:40:01

跟蹤訪問節點是DFS的一個重要組成部分（除非你有一個圖表管理了太多的節點），無論程序的其他部分是否需要它。否則，除非您需要檢查所有可能的路徑，否則最終會跟隨很多不是真正需要的相同節點的路徑。這就是我建議通過CLRS的原因。現在，你只是通過限制最大路徑長度來避免週期。這不是一個真正的解決方案，你仍然可能會遇到在同一節點之間有很多路徑的大圖的問題。如果你對此感到滿意，那很好。 – MAK 2010-01-09 20:26:17

感謝您澄清。通過遵循這些要求，我必須找到從節點X到X的距離小於給定數量的不同路徑的數量。所以，解決方案看起來像：XDX，XEBX，XEBXDX，XDXEBX，XDEBX，XEBXEBX，XEBXEBXEBX。這意味着我必須潛入一個循環，例如XEBX，但也可以根據切斷條件跳出它。對於更好地瞭解我現在正在採用的方法，即允許重新訪問節點，會非常感興趣。 – denchr 2010-01-09 20:39:19

只需在節點結構中添加一個額外的字段即「已訪問」字段。這將是最快的。之後您必須取消所有節點的標記（或在您執行搜索之前）。

或者，只是將散列表中的節點ID散列在一個散列表中。這將比堆棧檢查更快。如果您沒有該節點的ID，則最好創建一個，以幫助進行調試，輸出等。

您確實需要額外的空間，但向每個節點添加布爾字段將需要最小的空間，因爲它將是每個節點1位，而堆棧的每個節點只有1個指針。

因爲您正在搜索有限圖並且您只訪問每個節點一次，所以您不需要距離截斷點，因此您將在N節點圖中訪問至多N個節點。如果您正在搜索無限空間，例如進行狀態空間搜索時（例如尋找證明的序言解釋器），則需要深度中斷。

來源

2010-01-09 22:11:19

您不需要訪問節點。只需將當前子節點傳遞給遞歸方法而不是訪問節點參數，並使用返回值來攜帶路徑。

如果可以按元素處理路徑元素，即重寫printPath（），以便每個元素可以調用一次，只需要鍵類型作爲返回類型。如果你想接收整個路徑，你需要一個鍵值列表作爲返回類型。

其實，你比較接近解決方案。只需使用遞歸方法調用的調用堆棧來表示路徑即可。

來源

2010-01-13 17:31:40 Wolfgang

用於遞歸深度優先搜索以存儲路徑的額外空間

回答

相關問題