关于迷宫的深度优先遍历和广度优先遍历

  首先本次的迷宫为一个预设好的迷宫（有关于迷宫生成的文章，请翻我的目录），此迷宫有唯一解，分别采用递归的深度优先遍历和非递归的深度优先遍历，之外还有基于队列实现的广度优先遍历。算法采用java Swing 框架进行渲染，过程能实时的观看，比较的漂亮（想要代码的朋友请留言）。

基于递归的深度优先

// 从(x,y)的位置开始求解迷宫，如果求解成功，返回true；否则返回false
  private boolean go(int x, int y){
      
      //进来先判断x,y是否在data里面
      if(!data.inArea(x,y))
          throw new IllegalArgumentException("x,y are out of index in go function!");
      
      //把data中浏览过的设置为true
      data.visited[x][y] = true;
      //setData为javaSwing渲染的函数
      setData(x, y, true);
      //找到出口
      if(x == data.getExitX() && y == data.getExitY())
          return true;
      /**
       * 关键算法来了
       * 递归的深度优先遍历方法，无法就是每一步都往它的上下左右进行更进一步的深入
       * 所以我们想定义好一个上下左右的数组：int d[][] = {{-1,0},{0,1},{1,0},{0,-1}};
       * 然后就是下面的代码了，记得设置visited的坐标点
       */
      for(int i = 0 ; i < 4 ; i ++){
          int newX = x + d[i][0];
          int newY = y + d[i][1];
         //点x,y必须在区间内，然后是能走的路，而且这个点没有被visited过
          if(data.inArea(newX, newY) &&
                  data.getMaze(newX,newY) == MazeData.ROAD &&
                  !data.visited[newX][newY])
              if(go(newX, newY))
                  return true;
      }

      // 回溯
      setData(x, y, false);

      return false;
  }

效果图是这样的

image.png

基于非递归的深度优先

怎么说呢！在非递归的深度优先搜索中，那么肯定用到了栈结构对吧？所以呢，栈只能是碰壁之后就重写的回溯，然而不碰壁的，丫的也不会退出来的，所以在构造函数中记录节点的上一节点，但迷宫Slove的时候，用一个红线给标出来

private void run(){

      setData(-1, -1, false);

      Stack<Position> stack = new Stack<Position>();
      //封装迷宫的入口
      Position entrance = new Position(data.getEntranceX(), data.getEntranceY());
      stack.push(entrance);
      data.visited[entrance.getX()][entrance.getY()] = true;
      //isSolved是为了判断是否完成过程
      boolean isSolved = false;

      while(!stack.empty()){
          //这个curPos作为下一个节点的上一个节点
          Position curPos = stack.pop();
          setData(curPos.getX(), curPos.getY(), true);

          if(curPos.getX() == data.getExitX() && curPos.getY() == data.getExitY()){
              isSolved = true;
              findPath(curPos);
              break;
          }
          //关键算法还是差不多的，至少多了一个记录上次 节点的位置
          for(int i = 0 ; i < 4  ; i ++){
              int newX = curPos.getX() + d[i][0];
              int newY = curPos.getY() + d[i][1];

              if(data.inArea(newX, newY)
                      && !data.visited[newX][newY]
                      && data.getMaze(newX, newY) == MazeData.ROAD){
                  stack.push(new Position(newX, newY, curPos));
                  data.visited[newX][newY] = true;
              }
          }

      }

      if(!isSolved)
          System.out.println("The maze has no Solution!");

      setData(-1, -1, false);
  }

效果图是这样的

image.png

基于广度优先的搜索

广度优先搜索呢，其实就是把深度优先搜索的栈给换成队列，然后你喜欢用linkedList还是BlockQueue都行，看你喜欢
还是同样的问题，在java swing的渲染中，只能用一根红线表示，原因很简单，因为其它的我不会。

private void run(){

      setData(-1, -1, false);
      //用LinkedList实现队列
      LinkedList<Position> queue = new LinkedList<Position>();
      Position entrance = new Position(data.getEntranceX(), data.getEntranceY());
      //入队
      queue.addLast(entrance);
      data.visited[entrance.getX()][entrance.getY()] = true;

      boolean isSolved = false;

      while(queue.size() != 0){
          //出队
          Position curPos = queue.pop();
          setData(curPos.getX(), curPos.getY(), true);

          if(curPos.getX() == data.getExitX() && curPos.getY() == data.getExitY()){
              isSolved = true;
              findPath(curPos);
              break;
          }

          for(int i = 0 ; i < 4  ; i ++){
              int newX = curPos.getX() + d[i][0];
              int newY = curPos.getY() + d[i][1];

              if(data.inArea(newX, newY)
                      && !data.visited[newX][newY]
                      && data.getMaze(newX, newY) == MazeData.ROAD){
                  //上下左右符合的就入队吧
                  queue.addLast(new Position(newX, newY, curPos));
                  data.visited[newX][newY] = true;
              }
          }

      }

      if(!isSolved)
          System.out.println("The maze has no Solution!");

      setData(-1, -1, false);
  }

效果图是这样的（相对而言，广度的会把整个图遍历完）

image.png