StackOverflow錯誤：如何避免它或將此DFS轉換爲迭代？

Question

我使用深度優先搜索來生成迷宮。

M * N頂點的鄰接矩陣是使用DFS以隨機順序遍歷的，我只關心產生一個隨機路由。

事情正常工作與頂點的數量減少，但

Graph theGraph = new Graph(1000,1000); 

使用的問題時，我發現了一個StackOverflow的例外： 一）我怎樣才能改變這種迭代的遞歸調用使用堆棧？

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

關於（b）中，至少在Sun/Oracle的JVM，可以增加堆棧大小與-Xss命令行選項的JVM。

Answer 2

一些僞代碼：

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 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方法中。而不是遞歸它將填滿隊列中的四個方向中的一部分（我認爲最多3個），順序取決於random()結果。

Answer 4

我希望你會發現這個有用的。

您可以使用-Xss選項增加堆棧大小或重寫代碼。你可以在這裏得到一些想法。

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

代碼：

公共無效dfsPostOrderIterative（AdjGraph圖，AdjGraph.Node頂點，回撥回調）{ 堆棧toVisit =新堆棧（）; 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++; 
    } 
} 

}