深度优先搜索（DFS）

定义：

（*：https://en.wikipedia.org/wiki/Depth-first_search）

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

基本思想：

（1）访问顶点v；

（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；

（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

算法复杂度：

若有v个顶点、E条边，则

用邻接表储存图，有O(V+E)

用邻接矩阵储存图，有O(V^2)

伪代码：

递归实现：

（1）访问顶点v；visited[v]=1；//算法执行前visited[n]=0

（2）w=顶点v的第一个邻接点；

（3）while（w存在）

if（w未被访问）

从顶点w出发递归执行该算法；

w=顶点v的下一个邻接点；

//布尔型数组Visited[]初始化成false
void DFS(Vetex v)
{
    Visited[v] = true;
    for each w adjacent to v
        if (!Visited[w])
            DFS(w);
}

非递归实现：

（1）栈S初始化；visited[n]=0；

（2）访问顶点v；visited[v]=1；顶点v入栈S

（3）while(栈S非空)

x=栈S的顶元素(不出栈)；

if(存在并找到未被访问的x的邻接点w)

访问w；visited[w]=1；

w进栈;

else

x出栈;

//布尔型数组Visited[]初始化成false
void DFS(Vertex v)
{
    Visited[v] = true;
    Stack  sta = MakeStack(MAX_SIZE);
    Push(sta, v);
    while (!Empty(sta))
    {
        Vertex w = Pop(sta);
        for each u adjacent to w
        {
            if (!Visited[u])
            {
                Push(sta, u);
                Visited[u] = true;
            }
        }
    }
}

附：用C语言写一个走迷宫

具体内容为：

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

2、输入起点和终点坐标

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

 #include <stdio.h>

 char map[][];    //地图上限50*50
 int sign[][];     //标记
 int next[][]={{,},{,},{,-},{-,}};
 int n,m;    //实际地图行数、列数
 int endy,endx;     //终点位置
 int min=;

 /* run this program using the console pauser or add your own getch, system("pause") or input loop */

 //构造一个盏来记录走迷宫的路径
 struct Node
 {
     int y;
     int x;
 };

 struct Stack
 {
     Node * pbase;
     int top;
 };

 void StackInit(Stack * pstack){
     pstack->pbase=new Node[];
     pstack->top=;
 }

 void StackPush(Stack * pstack,int y,int x){
     Node node;
     node.y=y;
     node.x=x;
     pstack->pbase[pstack->top]=node;
     ++pstack->top;
 }

 void StackCopy(Stack * pstack1,Stack * pstack2){
     pstack2->top=pstack1->top;
     for(int i=;i<pstack2->top;i++)
     {
         pstack2->pbase[i]=pstack1->pbase[i];
     }
 }

 void StackPop(Stack * pstack){
     --pstack->top;
 } 

 Stack stack;
 Stack minstack;

 //深度优先搜索
 void dfs(int y,int x,int step){
     int ty,tx;
     if(y==endy&&x==endx)
     {
         if(step<min)
         {
             StackCopy(&stack,&minstack);
             min=step;
         }
         return;
     }

     for(int i=;i<;i++)
     {
         ty=y+next[i][];
         tx=x+next[i][];
         if(ty>=&&ty<n&&tx>=&&tx<m&&map[ty][tx]!='#'&&sign[ty][tx]==)
         {
             StackPush(&stack,ty,tx);
             sign[ty][tx]=;
             dfs(ty,tx,step+);
             StackPop(&stack);
             sign[ty][tx]=;
         }
     }
     return;
 }

 int main(int argc, char** argv) {
     printf("请输入行数和列数:");
     scanf("%d%d",&n,&m);
     printf("请创建地图:\n");
     for(int i=;i<n;i++)
     {
         scanf("%s",&map[i]);
     }
     printf("创建的地图如下:\n");
     for(int i=;i<n;i++)
     {
         printf("%s\n",map[i]);
     }
     printf("请输入起点(y,x):");
     int starty,startx;
     scanf("%d%d",&starty,&startx);
     printf("请输入终点(y,x):");
     scanf("%d%d",&endy,&endx);
     sign[starty][startx]=;

     StackInit(&stack);
     StackInit(&minstack);

     dfs(starty,startx,);
     printf("最短路程为%d\n",min);

     printf("最短路径为:\n");
     map[starty][startx]='s';    //用字符's'表示起点
     for(int i=;i<minstack.top;i++)
     {
         map[minstack.pbase[i].y][minstack.pbase[i].x]='>';
     }
     for(int i=;i<n;i++)
     {
         printf("%s\n",map[i]);
     }
     return ;
 }