我目前正在尝试通过自己创建图形类来制作游戏的图形表示。 构造函数就是这个(希望我这里没有任何逻辑错误):
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 的内容,它与缺乏可用内存有关,我知道这一点和我的问题不是这个。但我不明白为什么它会因为迭代器而发生在这里。即使对于彼此靠近的节点(仅进行几次递归调用)我也进行了尝试,并且出现了相同的错误。
最佳答案
在进入递归调用之前,检查您是否已经使用
覆盖了该节点....
int n = iterator.next();
if(!visited[n]){
...
}
关于由于 DFS 中的迭代器而导致 java.lang.StackOverflowError,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44356797/