我正在使用深度优先搜索进行迷宫生成。
使用DFS以随机顺序遍历M * N个顶点的邻接矩阵，我只对生成随机路由感兴趣。
在减少顶点数量的情况下，它可以很好地工作，但是在将它与以下对象一起使用时，出现了StackOverflow异常
Graph theGraph = new Graph(1000,1000);
问题：
a）如何使用堆栈将此递归调用更改为迭代调用？
b）是否可以为方法调用堆栈分配更多的内存？
class IJ {
int i;
int j;
IJ (int i,int j){
i = this.i;
j= this.j;
}
}
class Graph {
int M;
int N;
int adjacencyMatrix[][];
ArrayList <IJ> orderOfVisits;
Graph(int M,int N){
this.M=M;
this.N=N;
adjacencyMatrix=new int[M][N];
for (int i=0; i<M; i++)
for (int j=0;j<N;j++){
adjacencyMatrix[i][j]=-1; //mark all vertices as not visited
}
orderOfVisits = new ArrayList<IJ>();
}
void DFS(int i, int j){ // i,j identifies the vertex
boolean northValid= false;
boolean southValid= false;
boolean eastValid = false;
boolean westValid = false;
int iNorth, jNorth;
int iSouth, jSouth;
int iEast, jEast;
int iWest, jWest;
iNorth=i-1;
if (!(iNorth<0)) northValid=true;
iSouth=i+1;
if(!((iSouth)>=M)) southValid=true;
jEast=j+1;
if(!((jEast)>=N)) eastValid=true;
jWest= j-1;
if (!(jWest<0)) westValid=true;
if (adjacencyMatrix[i][j]==-1){ //if the vertex is unvisited
adjacencyMatrix[i][j]=0; //mark the vertex as visited
IJ ij = new IJ(i,j);
orderOfVisits.add(ij); //add the vertex to the visit list
System.out.println("Visit i,j: " + i +" " +j);
Double lottery = Math.random();
for (int rows=i; rows<M; rows++)
for (int cols=j; cols<N; cols++){
if (lottery>0.75D){
if(northValid)
{
DFS(iNorth,j);
}
if(southValid){
DFS(iSouth,j);
}
if(eastValid){
DFS(i, jEast);
}
if(westValid){
DFS(i,jWest);
}
}
else if (lottery<0.25D)
{
if(westValid){
DFS(i,jWest);
}
if(eastValid){
DFS(i, jEast);
}
if(southValid){
DFS(iSouth,j);
}
if(northValid)
{
DFS(iNorth,j);
}
}
else if ((lottery>=0.25D)&&(lottery<0.5D))
{
if(southValid){
DFS(iSouth,j);
}
if(eastValid){
DFS(i, jEast);
}
if(westValid){
DFS(i,jWest);
}
if(northValid){
DFS(iNorth,j);
}
}
else if ((lottery>=0.5D)&&(lottery<=0.75D))
{
if(eastValid){
DFS(i, jEast);
}
if(westValid){
DFS(i,jWest);
}
if(southValid){
DFS(iSouth,j);
}
if(northValid){
DFS(iNorth,j);
}
}
}
} //end nested for
} //end DFS
//
}
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Graph theGraph = new Graph(1000,1000);
theGraph.DFS(0,0);
}
}
最佳答案
一些伪代码：
Stack<IJ> nodesToVisit;
nodesToVisit.Push(new IJ(0, 1));
nodesToVisit.Push(new IJ(1, 0));
while (nodesToVisit.Count > 0)
{
var ij = nodesToVisit.Pop();
if (visited ij)
continue;
.... mark ij visited
... check north/south/east/west validity
List<IJ> directions = new List<IJ>();
if (canGoNorth)
directions.Add(new IJ(iNorth, j));
if (canGoSouth)
directions.Add(new IJ(iSouth, j));
if (canGoEast)
directions.Add(new IJ(i, jEast));
if (canGoWest)
directions.Add(new IJ(i, jWest));
... randomize list
foreach (direction in directions)
nodesToVisit.Push(direction);
}
基本上：
以随机顺序将所有可能的方向推入堆栈
选择顶项
去那里
重复直到堆栈为空（不再访问更多节点）
我不认为增加堆栈限制不是解决问题的好方法。