由於DFS中的迭代器導致的java.lang.StackOverflowError

我目前正在嘗試通過自己創建圖形類來製作遊戲的圖形再聲明。構造是這樣的一個（希望我不要在這裏有任何邏輯錯誤）：由於DFS中的迭代器導致的java.lang.StackOverflowError

private int nNodes; 
    private int nEdges; 
    private List<Integer> adj[]; 
    private boolean visited[]; 

    public GameGraph() 
    { 
     nNodes = 81; 
     adj = new LinkedList[nNodes]; 
     for(int i = 0; i < nNodes; i++) 
      adj[i] = new LinkedList(); 
     visited = new boolean[nNodes]; 
    }

我檢查是否存在使用深度優先搜索算法源和目的地之間的路徑。這是我寫的：

public boolean hasPath(int source , int dest) 
     { 
      if(source >= nNodes) 
       return false; 
      else 
      { 
       visited[source] = true; 

       try 
       { 
        Iterator<Integer> iterator = adj[source].listIterator(); 
        while(iterator.hasNext()) 
        { 
         int n = iterator.next(); 
         if(n == dest) 
          return true; 
         visited[n] = true; 
         if(hasPath(n, dest)) 
          return true; 
        }//end while 
        return false; 
       }//end try 
       catch(NullPointerException exception) 
       { 
        exception.printStackTrace(); 
       }//end catch 

       return false; 
      }//end else 
     }//end method has path

的問題是，當我運行在主類這種方法，我有這樣的錯誤：

Exception in thread "main" java.lang.StackOverflowError 
    at java.util.LinkedList$ListItr.<init>(Unknown Source) 
    at java.util.LinkedList.listIterator(Unknown Source) 
    at java.util.AbstractList.listIterator(Unknown Source) 
    at java.util.AbstractSequentialList.iterator(Unknown Source) 
    at logic.GameGraph.hasPath(GameGraph.java:67) 
    at logic.GameGraph.hasPath(GameGraph.java:74)at logic.GameGraph.hasPath(GameGraph.java:74) 
    at logic.GameGraph.hasPath(GameGraph.java:74) 
    at logic.GameGraph.hasPath(GameGraph.java:74)

線67：

Iterator<Integer> iterator = adj[source].listIterator();

而第74行是遞歸調用：

if(hasPath(n, dest))

我閱讀了關於StackOverflowError，它與可用內存不足有關，我知道一個和我的問題不是這樣。但我不明白爲什麼它應該在這裏發生迭代器的原因。我嘗試過，即使只有幾個遞歸調用的節點彼此靠近，也會發生相同的錯誤。

來源

2017-06-04 Joan Plepi

你從來沒有請檢查是否或不是你alraedy訪問節點。你只把它標記爲viisited，但是當你再次遇到它時，你再次檢查它=>無限遞歸。 – Polygnome

在方法'hasPath（）'的開頭添加'println（）'語句，打印這兩個參數。輸出將有助於確定代碼失敗的原因。這被稱爲**調試**。您可能還想閱讀「[什麼是調試器，它如何幫助我診斷問題？]（https://stackoverflow.com/q/25385173/5221149）」，儘管簡單的'print'語句可能更容易看問題的方法。 – Andreas

@Polygnome是的，你是對的，謝謝 –

之前進入遞歸調用檢查，如果你已經涵蓋了該節點使用

.... 
int n = iterator.next(); 
if(!visited[n]){ 
... 
}

來源

2017-06-04 17:33:48

謝謝，我注意到它太晚了 –

由於DFS中的迭代器導致的java.lang.StackOverflowError

回答

相關問題