数据结构之深度优先搜索（用栈实现）问题

深度优先搜索

可以这样理解，向四边延伸搜索，然后遇到不能搜索的时候就回退，也就是回溯思想，然后再去其它可能地方搜索。

题目：

定义一个二维数组：

int maze[5][5] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。程序如下：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define MAX_ROW 5
     
    
   

    

     

    
    

     

      #define MAX_COL 5
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int top = 0;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      struct Node {
     
    
   

    

     

    
    

     

       int row;
     
    
   

    

     

    
    

     

       int col;
     
    
   

    

     

    
    

     

      } stack[512];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int maze[MAX_ROW][MAX_COL] = {
     
    
   

    

     

    
    

     

       0, 1, 0, 0, 0,
     
    
   

    

     

    
    

     

       0, 1, 0, 1, 0,
     
    
   

    

     

    
    

     

       0, 0, 0, 0, 0,
     
    
   

    

     

    
    

     

       0, 1, 1, 1, 0,
     
    
   

    

     

    
    

     

       0, 0, 0, 1, 0,
     
    
   

    

     

    
    

     

      };
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void push_stack(struct Node node)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       stack[top++] = node;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      struct Node pop_stack()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       return stack[--top];
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int is_empty() {
     
    
   

    

     

    
    

     

         return top == 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void printf_stack()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       for (int i &
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/54136375