StackOverflow 错误：如何避免它或将此 DFS 转变为迭代 DFS？

Question

我正在使用深度优先搜索来生成迷宫。

使用DFS以随机顺序遍历M*N顶点的邻接矩阵，我只对生成随机路线感兴趣。

这个东西在顶点数量减少的情况下工作得很好，但是当我将它与

 Graph theGraph = new Graph(1000,1000);

问题一起使用时，我遇到了 StackOverflow 异常： 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);



    }

}

Answer 1

一些伪代码：

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);
}

基本上：

• 按随机顺序推送堆栈上的所有可能方向
• 选择顶部项目
• 前往那里
• 重复直到堆栈为空（也不再需要访问更多节点）

我不认为增加堆栈限制是一个很好的解决方案你的问题。

Answer 2

对于 (b)，至少对于 Sun/Oracle JVM，您可以使用 JVM 的 -Xss 命令行选项来增加堆栈大小。

Answer 3

您必须将递归实现转换为迭代实现。通常（我也认为这里）递归算法比做同样事情的迭代算法更容易理解。

原则上，您需要用包含必要信息的显式数据结构（堆栈等）来替换 Java 方法调用堆栈。

在您的情况下，它将是当前节点，以及要访问的剩余邻居节点的列表（按应访问的顺序排列）。

class DFSNode {
   DFSNode parent;
   int x, y;
   Queue<Direction> neighborsToVisit;
   DFSNode(DFSNode p, int x, int y) {
      this.parent = p; this.x = x; this.y = y;
      this.neighborsToVisit = new ArrayDeque(3);
   }
}

enum Direction {

   // TODO: check the numbers
   NORTH(0,1), SOUTH(0,-1), EAST(1,0), WEST(-1,0);

   Direction(int dX, dY) {
      deltaX = dX; deltaY = dY;
   }

   private int deltaX, deltaY;

   int nextX(int x) { return x + deltaX; }
   int nextY(int y) { return y + deltaY; }
}

void visitNode(DFSNode node) {
    // TODO: check which adjacent directions are valid,
    // randomize the order of these adjacent directions,
    // fill them in the queue.
}

void visitGraph(int x, int y) {
   DFSNode currentNode = new DFSNode(null,x,y);
   visitNode(currentNode);
   while(currentNode != null) {
      Direction dir = currentNode.neighboursToVisit.poll();
      if(dir == null) {
         // all neighbours of this node already visited
         // ==> trackback to parent (and end if this is root node)
         currentNode = currentNode.parent;
         continue;
      }
      currentNode = new DFSNode(currentNode, dir.nextX(currentNode.x), dir.nextY(currentNode.y));
      visitNode(currentNode);
   }
}

visitNode 将包含主要逻辑，即 DFS 方法中现在的内容。它不会递归，而是按照由 random() 结果确定的顺序，用四个方向中的一些（我认为最多 3 个）填充队列。

Answer 4

我希望您会发现这很有帮助。

您可以使用 -Xss 选项增加堆栈大小或重写代码。您可以在这里得到一些想法。

http://www.vvlasov.com/2013/07 /post-order-iterative-dfs-traversal.html

代码：

public void dfsPostOrderIterative(AdjGraph graph, AdjGraph.Node vertex,回调回调）{
访问堆栈 = new Stack();
toVisit.push(new Level(Collections.singletonList(vertex)));

while (!toVisit.isEmpty()) {
    Level level = toVisit.peek();

    if (level.index >= level.nodes.size()) {
        toVisit.pop();
        continue;
    }

    AdjGraph.Node node = level.nodes.get(level.index);

    if (!node.isVisited()) {
        if (node.isChildrenExplored()) {
            node.markVisited();
            callback.nodeVisited(graph, node);
            level.index++;
        } else {
            List<AdjGraph.Node> edges = graph.edges(node);
            List<AdjGraph.Node> outgoing = Lists.newArrayList(Collections2.filter(edges, new Predicate<AdjGraph.Node>() {
                @Override
                public boolean apply(AdjGraph.Node input) {
                    return !input.isChildrenExplored();
                }
            }));

            if (outgoing.size() > 0)
                toVisit.add(new Level(outgoing));
            node.markChildrenExplored();
        }
    } else {
        level.index++;
    }
}

}