定义：
（*：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 ;
}