DSF深度优先搜索：最短路径问题
DFS深度优先搜索原理：
深度优先搜索以”深度”作为第一关键词，每次都是沿着路径到不能再前进时才退回到最近的岔道口。
以一个有向图进行DFS 遍历来举例（从V0开始进行遍历，黑色表示结点未访问，白色表示结点已访问，虚线边表示当前遍历路径）;
① 访问 V0，发现从V0出发可以到达两个未访问顶点∶ V1和 V2，因此准备访问 V1和 V2这两个顶点。此时情况如图所示：
②从V0出发访问V1，发现从V1出发可以到达两个未访问顶点:V3和V4，因此准备访问V3和V4这两个顶点。此时情况如图所示：
③从V1出发访问V3，但是V3出发不能到达任何未访问顶点，因此退回当前路径上距离V3最近的仍有未访问分支顶点的岔道口V1。此时情况如图所示：
④从V1出发访问V4，发现从 V4出发可以到达一个未访问顶点∶V5，因此准备前往访问V5。此时情况如图所示：
⑤ 从V4出发访问V5，发现从 V5出发不能到达任何未访问顶点，因此退回到当前路径上距离V5最近的仍有未访问分支顶点的岔道口V0。此时情况如图所示：
⑥ 从V0出发访问V2，发现从V2出发不能到达任何未访问顶点，因此退回到当前路径上距离V5最近的仍有未访问分支顶点的岔道口。但是此时路径上所有顶点的分支顶点都已被访问，因此 DFS 算法结束。此时情况如图所示：
因此，DFS被形容为一条路走到黑，不撞南墙不回头。
沿着一条路径直到无法继续前进，才退回到路径上离当前顶点最近还存在未访问分支顶点的岔道口，并前往访问那些未访问分支顶点，直到遍历完整个图。
实战代码部分：
整体代码：
#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
int book[51][51]; //检索坐标
int a[51][51]; //通路与障碍坐标
int maze[51][51]; //路径二维坐标
int n,m,p,q,min = 99999;//初始化最小值min
int path1[51],path2[51];//保存路径的x，y坐标
/*
int a[51][51] = {
{0,0,1,0,1,0,0},
{1,0,0,0,0,1,0},
{0,0,1,1,0,0,0},
{1,0,0,1,1,1,0},
{0,0,0,0,0,0,0},
{1,1,0,0,1,0,1},
{1,0,0,0,0,0,1},
};*/
/*创建移动方向*/
int next[4][2] = {
{0,1}, //right
{1,0}, //up
{0,-1}, //left
{-1,0} //down
};
void dfs(int x ,int y,int step){ //DFS深度优先
int tx,ty,k; //形参
if(x == q && y == p){ //出口，找到目标，登出
if(step < min){ //更新最短路径
min = step;
for(int i = 0; i < step; i++)printf("(%d,%d)",path1[i],path2[i]); //打印一维路径
for(int i = 0; i < n; i++){ //清除maze缓存
for(int j = 0; j < m; j++){
maze[i][j] = 0;
}
}
for(int i = 0; i < step; i++){ //由两个一维数组可构建一个二维数组
maze[path1[i]][path2[i]] = 5; //赋值5代表路径
}
printf("path = %d\n",min); //打印最小值
printf("\n");
}
return ; //此时的return代表返回上一步
}
for(k = 0; k <= 3; k++){ //移动方向，
tx = x + next[k][0]; //当前x加即将移动方向
ty = y + next[k][1]; //当前y加即将移动方向
if(tx < 1 || tx > n || ty < 1 || ty > m) //是否越界，越界跳出循环
continue;
if(a[tx][ty] == 0 && book[tx][ty] == 0){ //a代表障碍，0表示无，book代表是否检索过，0代表未
book[tx][ty] = 1; //表示该坐标已检索
path1[step] = tx; //缓存x
path2[step] = ty; //缓存y
dfs(tx,ty,step+1);//进入下一步DFS
/*以下是回溯，这里代表return后的步骤，即回溯*/
book[tx][ty] = 0; //已经回溯，还原该坐标，代表未检索
}
}
return ;
}
int main(){
int i,j,startx,starty;
printf("矩阵大小：");
scanf("%d %d",&n,&m);
printf("起始位置：");
scanf("%d %d",&startx,&starty);
printf("目标位置：");
scanf("%d %d",&q,&p);
book[startx][starty] = 1;//标记起始位置为已检索，在路径中不会显示起始位置，注释，即可显示
for(i = 0; i < n; i++){ //初始化
for(j = 0; j < m; j++){
a[i][j] = 0;
a[rand()%7][rand()%7] = 1;//随机生成墙
}
}
for(i = 0; i < n; i++){ //初始化
for(j = 0; j < m; j++){
maze[i][j] = 0;
if((i == startx) && (j == starty))a[i][j] = 0;
if((i == q) && (j == p))a[i][j] = 0;
}
}
dfs(startx,starty,0); //DFS深度优先开始，从起始位置，步数0开始
for(int heng = 0; heng < n; heng++){ //打印二维路径
for(int shu = 0; shu < m; shu++){
if(a[heng][shu] == 1) maze[heng][shu] = 1;
printf("%d",maze[heng][shu]);
}printf("\n");
}printf("\n");
return 0;
}
解析代码：
int book[51][51];
int a[51][51];
int maze[51][51]; //路径二维坐标
int n,m,p,q,min = 99999;//初始化最小值min
int path1[51],path2[51];//保存路径的x，y坐标
/*
int a[51][51] = {
{0,0,1,0,1,0,0},
{1,0,0,0,0,1,0},
{0,0,1,1,0,0,0},
{1,0,0,1,1,1,0},
{0,0,0,0,0,0,0},
{1,1,0,0,1,0,1},
{1,0,0,0,0,0,1},
};*/
/*创建移动方向*/
int next[4][2] = {
{0,1}, //right
{1,0}, //up
{0,-1}, //left
{-1,0} //down
};
创建一个二维数组，代表四个方向的移动意图。
int main(){
//手动输入
int i,j,startx,starty;
printf("矩阵大小：");
scanf("%d %d",&n,&m);
printf("起始位置：");
scanf("%d %d",&startx,&starty);
printf("目标位置：");
scanf("%d %d",&q,&p);
book[startx][starty] = 1;//标记起始位置为已检索，在路径中不会显示起始位置，注释，即可显示
//初始化，将a[][]赋值0代表可通过，1代表墙
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
a[i][j] = 0;
a[rand()%7][rand()%7] = 1;//随机生成墙
}
}
//初始化，maze代表走过的路径，1：走过，0：未走过
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
maze[i][j] = 0;
if((i == startx) && (j == starty))a[i][j] = 0;
if((i == q) && (j == p))a[i][j] = 0;
}
}
dfs(startx,starty,0); //DFS深度优先开始，从起始位置，步数0开始
//最后打印最短路径
for(int heng = 0; heng < n; heng++){ //打印二维路径
for(int shu = 0; shu < m; shu++){
if(a[heng][shu] == 1) maze[heng][shu] = 1;
printf("%d",maze[heng][shu]);
}printf("\n");
}printf("\n");
return 0;
}
以下是DFS函数
void dfs(int x ,int y,int step){ //DFS深度优先
int tx,ty,k; //形参
if(x == q && y == p){ //出口，找到目标，登出
if(step < min){ //更新最短路径
min = step;
for(int i = 0; i < step; i++)printf("(%d,%d)",path1[i],path2[i]); //打印一维路径
for(int i = 0; i < n; i++){ //清除maze缓存
for(int j = 0; j < m; j++){
maze[i][j] = 0;
}
}
for(int i = 0; i < step; i++){ //由两个一维数组可构建一个二维数组
maze[path1[i]][path2[i]] = 5; //赋值5代表路径
}
printf("path = %d\n",min); //打印路径步数
printf("\n");
}
return ; //此时的return代表返回上一步
}
for(k = 0; k <= 3; k++){ //移动方向，
tx = x + next[k][0]; //当前x加即将移动方向
ty = y + next[k][1]; //当前y加即将移动方向
if(tx < 1 || tx > n || ty < 1 || ty > m) //是否越界，越界跳出循环
continue;
if(a[tx][ty] == 0 && book[tx][ty] == 0){ //a代表障碍，0表示无，book代表是否检索过，0代表未
book[tx][ty] = 1; //表示该坐标已检索
path1[step] = tx; //缓存x
path2[step] = ty; //缓存y
dfs(tx,ty,step+1);//进入下一步DFS
/*以下是回溯，这里代表return后的步骤，即回溯*/
book[tx][ty] = 0; //已经回溯，还原该坐标，代表未检索
}
}
return ;
}
输入：
矩阵大小：7 7
起始位置：2 1
目标位置：5 6
输出：
(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)(3,7)(4,7)(5,7)(6,7)(7,7)(7,6)(7,5)(7,4)(7,3)(7,2)(7,1)(6,1)(6,2)(6,3)(6,4)(6,5)(6,6)(5,6)path = 24
(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)(3,7)(4,7)(5,7)(6,7)(7,7)(7,6)(7,5)(7,4)(7,3)(7,2)(6,2)(6,3)(6,4)(6,5)(6,6)(5,6)path = 22
(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)(3,7)(4,7)(5,7)(6,7)(7,7)(7,6)(7,5)(7,4)(7,3)(6,3)(6,4)(6,5)(6,6)(5,6)path = 20
(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)(3,7)(4,7)(5,7)(6,7)(7,7)(7,6)(7,5)(7,4)(6,4)(6,5)(6,6)(5,6)path = 18
(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)(3,7)(4,7)(5,7)(6,7)(7,7)(7,6)(7,5)(6,5)(6,6)(5,6)path = 16
(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)(3,7)(4,7)(5,7)(6,7)(7,7)(7,6)(6,6)(5,6)path = 14
(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)(3,7)(4,7)(5,7)(6,7)(6,6)(5,6)path = 12
(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)(3,7)(4,7)(5,7)(5,6)path = 10
(2,2)(3,2)(4,2)(5,2)(5,3)(5,4)(5,5)(5,6)path = 8
0111111
0110111
0050000
1051111
0151100
1055555
0000000
0代表可通过的路，1代表墙，不可通过的路，5代表最终的最短路径。
注意，标记起始位置为已检索，在路径中不会显示起始位置，若要显示，阅读主函数中book[startx][starty]部分。
版权声明：本文为weixin_46369610原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。