转载

深度优先算法——走迷宫的实现

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。

因发明“深度优先搜索算法”，霍普克洛夫特与陶尔扬共同获得计算机领域的最高奖：图灵奖.

学以致用，为了在实践中学习，我用深度优先算法写了一个走迷宫的小程序。

具体内容为：

1、输入长宽和迷宫地图（‘#’代表墙，‘.'代表空地）

2、输入起点和终点坐标

3、用深度优先算法查找起点到终点的最短路径并显示出来

下面是具体C语言实现：

1 #include <stdio.h>   2    3 char map[50][51];    //地图上限50*50    4 int sign[50][50];     //标记    5 int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};   6 int n,m;    //实际地图行数、列数    7 int endy,endx;     //终点位置    8 int min=99999999;   9   10 /* run this program using the console pauser or add your own getch, system("pause") or input loop */  11   12 //构造一个盏来记录走迷宫的路径  13 struct Node  14 {  15     int y;  16     int x;  17 };  18   19 struct Stack  20 {  21     Node * pbase;  22     int top;  23 };  24   25 void StackInit(Stack * pstack){  26     pstack->pbase=new Node[100];  27     pstack->top=0;  28 }  29   30 void StackPush(Stack * pstack,int y,int x){  31     Node node;  32     node.y=y;  33     node.x=x;  34     pstack->pbase[pstack->top]=node;  35     ++pstack->top;  36 }  37   38 void StackCopy(Stack * pstack1,Stack * pstack2){  39     pstack2->top=pstack1->top;  40     for(int i=0;i<pstack2->top;i++)  41     {  42         pstack2->pbase[i]=pstack1->pbase[i];  43     }  44 }  45   46 void StackPop(Stack * pstack){  47     --pstack->top;  48 }   49   50 Stack stack;  51 Stack minstack;  52   53 //深度优先搜索   54 void dfs(int y,int x,int step){  55     int ty,tx;  56     if(y==endy&&x==endx)  57     {  58         if(step<min)  59         {  60             StackCopy(&stack,&minstack);  61             min=step;  62         }  63         return;  64     }  65       66     for(int i=0;i<4;i++)  67     {  68         ty=y+next[i][0];  69         tx=x+next[i][1];  70         if(ty>=0&&ty<n&&tx>=0&&tx<m&↦[ty][tx]!='#'&&sign[ty][tx]==0)  71         {  72             StackPush(&stack,ty,tx);  73             sign[ty][tx]=1;  74             dfs(ty,tx,step+1);  75             StackPop(&stack);  76             sign[ty][tx]=0;  77         }  78     }  79     return;  80 }  81   82 int main(int argc, char** argv) {  83     printf("请输入行数和列数:");  84     scanf("%d%d",&n,&m);  85     printf("请创建地图:/n");  86     for(int i=0;i<n;i++)  87     {  88         scanf("%s",↦[i]);  89     }  90     printf("创建的地图如下:/n");  91     for(int i=0;i<n;i++)  92     {  93         printf("%s/n",map[i]);   94     }  95     printf("请输入起点(y,x):");  96     int starty,startx;  97     scanf("%d%d",&starty,&startx);  98     printf("请输入终点(y,x):");  99     scanf("%d%d",&endy,&endx); 100     sign[starty][startx]=1; 101      102     StackInit(&stack); 103     StackInit(&minstack); 104  105     dfs(starty,startx,0);  106     printf("最短路程为%d/n",min); 107      108     printf("最短路径为:/n"); 109     map[starty][startx]='s';    //用字符's'表示起点  110     for(int i=0;i<minstack.top;i++) 111     { 112         map[minstack.pbase[i].y][minstack.pbase[i].x]='>'; 113     } 114     for(int i=0;i<n;i++) 115     { 116         printf("%s/n",map[i]);  117     }     118     return 0; 119 }

运行结果如图（’>'表示最短路径,'s'表示起点）

深度优先算法——走迷宫的实现