深度優先搜索運行到java.lang.OutOfMemoryError

我遇到一個java.lang.OutOfMemoryError當我使用一個無向圖的深度優先搜索，以確定是否節點1是可達節點2。代碼如下所示。（一些無關痛癢的細節旨在被刪除。）深度優先搜索運行到java.lang.OutOfMemoryError

//definition of nodes and edges 
    Set<Node> nodes = new HashSet<Node>(); 
    Map<Node, Set<Node>> edges = new HashMap<Node, Set<Node>>(); 

    //method to determine if node1 is reachable to node2  
    public boolean isReachable(int p1, MethodNode m1, ClassNode c1, int p2, MethodNode m2, ClassNode c2) { 
      Node node1 = new Node (p1,m1,c1); 
     Node node2 = new Node (p2,m2,c2); 

      Stack<Node> stack = new Stack<Node>(); 

     stack.push(node1); 
     while(!stack.isEmpty()){ 

      Node current = null; 
      current = stack.pop(); 
        //test current node, if its child nodes contains node2, return true 
        //otherwise, push its child nodes into stack 
      for(final Node temp : edges.get(current)){ 
       if(temp.equals(node2)){ 
        return true; 
       } 
       else{ 
        stack.push(temp); 
       } 
      } 
     } 
     return false; 
}

我想一定是跑出來的一些內存無限通話，但我不能找到它。

來源

2013-02-07 Bing Lu

爲什麼不使用dijstras最短路徑算法？ – AlexWien

我只是嘗試實現DFS和BFS來熟悉Java中的Stack和Queue。 @AlexWien –

這是問題

for (final Node temp : edges.get(current)){ 
    if(temp.equals(node2)){ 
     return true; 
    } else { 
     stack.push(temp); 
    } 
}

這將推動在堆棧上的所有鄰居，然後採取其中的一種，推棧上的所有鄰國（包括你開始在一個），等廣告無窮。您需要將節點標記爲已訪問，因此不會發生。唯一不會遇到無限循環的情況是，當您要查找的節點與您開始的節點直接相鄰或者路徑上的節點以正確的順序放入堆棧時純粹的機會。

來源

2013-02-07 02:57:51

明確的解釋。非常感謝。我已經想出了這個問題。 @ G.Bach –

您的算法，如果有圖有一個週期，這將持續推動該週期的元素壓入堆棧，直到你耗盡內存。您需要跟蹤哪些節點已經被探測並避免將它們推入堆棧。有幾種標準算法可以做到這一點（A ^*和Dijkstra浮現在腦海中）。有關更多信息，請參見depth first search上的維基百科文章。

來源

2013-02-07 02:56:23

它看起來像你的代碼容易受到追逐自己的尾巴：如果一個圖包含一個週期，你的代碼將耗盡堆棧，因爲如果一個頂點已推到堆棧中之前被探索它不檢查。

Basic DFS需要你保持一組頂點探索，探索頂點，只有當它是未知。將此組添加到程序中應該解決內存不足的問題。

來源

2013-02-07 02:56:25 dasblinkenlight

謝謝。 G.Bach和你都給我很好的幫助。選擇最佳答案真的很難。 @dasblinkenlight –

嘗試使用一個額外的

列表<節點>遍歷=新的ArrayList <節點>（）;

在這裏，你可以保留你正在推入堆棧的節點。在將其推入堆棧前執行1步

if(!traversed.contains(temp)) { 
stack.push(temp); 
}

來源

2013-02-07 06:42:31

深度優先搜索運行到java.lang.OutOfMemoryError

回答

相關問題