java.lang.StackOverflowError 由于 DFS 中的迭代器

Question

我目前正在尝试通过自己创建图表 class 来制作游戏的图表表示。构造函数是这个（希望我这里没有任何逻辑错误）：

 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

问题是当我运行这个方法在 main class 中时，我有这个错误：

Exception in thread "main" java.lang.WhosebugError
    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))

我读到了有关 WhosebugError 的信息，它与可用内存不足有关，我明白这一点，而我的问题不是那个。但我不明白为什么它应该在这里发生迭代器的原因。我什至对彼此靠近的节点进行了尝试，这些节点只进行了几次递归调用，并且发生了同样的错误。

Answer 1

在进入递归调用之前，请检查您是否已经使用

覆盖了该节点

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

java.lang.StackOverflowError 由于 DFS 中的迭代器

java.lang.StackOverflowError due to iterator in DFS

java

stack-overflow

recursion

iterator