戏说深度优先算法（代码）

因为CSDN不能上传图片，故效果有所折扣 
原文连接：http://blog.sina.com.cn/fulaoshi  终于要说到代码实现了，深度优先搜索的原理不难理解，但要用代码实现，也有点小难度，下面对各个难点进行说明：1， 地图（迷宫）的表示
一般可以使用整形二维数组描述地图，0代表空地，1代表墙，2代表出口，3代表走过的路。有点浪费内存，但是易于理解。
2， 下一步选择（方向）的表示
一般使用连续的整形，如表示“上下左右”四个方向就可用1，2，3，4来代替
3， 记录每一步选择（毛线）
上一章说过，可以使用栈或者一维数组进行记录给出伪代码：
构建地图
定义变量x，y代表当前位置，初始值为迷宫入口处
循环开始
A：
尝试下一个方向
如果 （下一个方向==→） xx = x + 1, yy = y
如果 （下一个方向==↑） xx = x , yy = y - 1
如果 （下一个方向==←） xx = x - 1, yy = y
如果 （下一个方向==↓） xx = x , yy = y + 1
如果 （四个方向都尝试过了）
如果栈为空，失败，没有出口，跳出循环
出栈，获取上一次的方向
跳到A判断地图上的xx，yy坐标内容
如果是出口，获胜，跳出循环
如果是墙或走过的路，跳到A
如果是空地
当前方向入栈
x = xx，y = yy    //前进一步
在地图上将x，y坐标标记为走过的路
判断结束
循环结束下面贴出完整代码，比较长，做好心理准备。public class DFS {
//辅助方法：打印地图
private static void printArray(int m[][]) {
int v = 0;
for (int y=0;y<10;y++) {
for (int x = 0;x<10; x++) {
v = m[y][x];
if (v==0) System.out.print("  ");
if (v==1) System.out.print("■■");
if (v==2) System.out.print("XX");
if (v==3) System.out.print("  ");
if (v==11) System.out.print("->");
if (v==12) System.out.print("^^");
if (v==13) System.out.print("<-");
if (v==14) System.out.print("vv");
}
System.out.println();
}
} public static void main(String[] args) {
//初始化地图，数组中1代表墙，0代表路，2是出口，3是走过的路
int[][] map = {
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,2},
{1,0,1,0,1,0,1,1,1,1},
{1,0,1,0,1,0,1,0,0,1},
{1,1,1,1,1,0,1,1,0,1},
{1,0,0,0,0,0,0,1,0,1},
{1,1,1,1,1,1,0,1,0,1},
{1,1,1,1,1,1,0,1,0,1},
{0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
System.out.println("原始地图");
printArray(map);
//初始化地图完毕
int d[] = new int[100]; //记录每一步的方向（毛线）
int step = 0; //已经走了多少步
int dir = 0; //方向：1，2，3，4分别代表右、上、左、下
int startX = 0, startY = 8; //迷宫的入口坐标
int x = startX ,y = startY;
int xx=0, yy=0;

//开始进入迷宫
do {
dir++; //试探下一个方向
if (dir>4) {
//回朔
if (step==0) {
System.out.println("地图没有出口！");
return;
}
dir = d[step-1]; //取出上一次的方向
//沿着反方向后退一步
if (dir==1) x--;
if (dir==2) y++;
if (dir==3) x++;
if (dir==4) y--;
step--;
continue;
}
//按照方向前进一步
xx = x; yy = y;
if (dir==1) xx++;
if (dir==2) yy--;
if (dir==3) xx--;
if (dir==4) yy++;

if (map[yy][xx]==2) {
d[step] = dir;
System.out.println("找到出口");
break;
}
if (map[yy][xx]!=0) {
//撞墙了或遇到走过的路
continue;
} else {
//记录当前方向
d[step] = dir;
dir = 0;
map[y][x] = 3; //堵回头路
x = xx;
y = yy;
step++;
}
} while (true);
//下面为结果输出
System.out.println("一共走了" + step + "步!"); x = startX;
y = startY;
map[y][x] = d[0] + 10;
for (int i = 0; i <= step; i++) {
if (d[i]==1) x++;
if (d[i]==2) y--;
if (d[i]==3) x--;
if (d[i]==4) y++;
map[y][x] = d[i]+10;
}
printArray(map);
}
}运行结果如下：
原始地图
■■■■■■■■■■■■■■■■■■■■
■■                   XX
■■  ■■  ■■   ■■■■■■■■
■■  ■■  ■■   ■■     ■■
■■■■■■■■■■  ■■■■   ■■
■■              ■■   ■■
■■■■■■■■■■■■  ■■   ■■
■■■■■■■■■■■■  ■■   ■■
                      ■■
■■■■■■■■■■■■■■■■■■■■
找到出口
一共走了17步!
■■■■■■■■■■■■■■■■■■■■
■■          ||->->->->
■■  ■■  ■■ ||■■■■■■■■
■■  ■■  ■■ ||■■     ■■
■■■■■■■■■■||■■■■   ■■
■■          <-||■■   ■■
■■■■■■■■■■■■||■■   ■■
■■■■■■■■■■■■||■■   ■■
->->->->->->->     ■■
■■■■■■■■■■■■■■■■■■■■现在我写这些代码算比较轻松了，但回想N年前刚学习深度优先时，虽然理论上明白了，但是代码死活也整合不到一块儿去，动不动就数组下标越界或者死循环，希望大家练习这部分代码的时候一定要有耐心，再加上细心。 至此，深度优先搜索算法已经介绍了75%了，剩下的25%，也就是第四部分，我会介绍它的应用，不仅仅只是能走迷宫哦。