Java 深度搜索DFS算法
java舞动乾坤 人气:0DFS概述
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。
解释
思路
一般用矩阵表示，从当前点开始，依次向周围四个方向试探，在我们给定数值条件下依次搜索（1代表不能走，0代表能走），对走过的路进行标记，如果最终达到了要走的点，就会进行回溯，回溯时，会将已经走过的点再次标记为未走，回到出发点，进行别的方向的试探
当找到距离最短的，而且到达了终点时，停止访问，输出结果
案例题-单身的蒙蒙
题目描述
蒙蒙要找对象啦！但是对象在和他玩捉迷藏，现在有一个55的地图，蒙蒙就在（0，0）的位置，他的心上人就在（4，4）的位置，当然路上会有各种艰难险阻，现在说明一下规则。蒙蒙按照地图行动，一次走一步，而且他只能前后左右的移动，当然蒙蒙也不能穿越墙壁。地图上有两种图案，一种是‘0'表示可以走的路，另一种是‘1'表示不能走的墙
PS:（0，0）就是左上角，（4，4）就是右下角，都懂吧！
输入：
输入一个55的矩阵表示地图，‘0'表示可以走的路，‘1'表示不能走的墙，蒙蒙就在（0，0）的位置，他的心上人就在（4，4）的位置
输出：
输出蒙蒙到心上人那里最少要走多少步，若蒙蒙永远走不到心上人那里，则输出-1
输入样例：
0 1 0 0 0
0 0 0 1 0
0 1 0 1 0
0 1 0 0 0
0 0 0 1 0
输出样例：
8
题解
分析: 首先分析下，主人公要想能够找到对象，就需要走到左下角，而去的过程显然不是一帆风顺的，它会遇到墙壁，遇到墙壁就会返回，返回到前一个点之后向其他方向进行搜索，如果有通路，就会接着执行这步的操作，直到找到终点。题目中问的是最少要通过多少步才能找到对象，那么显然可能一次搜索找不到最短的路径，这里就需要回溯，把回溯的点设置为未标记，回溯到最初的点之后进行其他方向的遍历，如果第二次到达终点的值小于第一次的就更新路径，将第二次的路径作为最小的路径，直到所有点遍历完
//回溯算法 flag[xx][yy]=1//标记 dfs(1,1,step+1) //flag[xx][yy]=0;设置为未标记的点，进行回溯
方向数组 因为要进行四个方向的试探，所以要定义一个方向数组：方向数组的定义可以使用一维数组，亦可以使用二维数组，建议大家使用一维数组，直观明了，这里解释下便于方便，将标准坐标轴顺时针方向旋转了90度，令x=0;y=0则可有四个方向坐标 右：（0，1），下：（1，0），左：（0，-1），上：（-1，0），依次取dx一次，dy一次，就和上面的坐标一致了
static int[] dx = {0, 1, 0, -1};//方向数组，顺时针：右 下 左 上
static int[] dy = {1, 0, -1, 0};
注意事项: 这里因为输入的是从原点开始，而外界临界值也是等同于墙壁，为了免去试探，可以将四边的设置为“1”墙壁，这样可以避免数组越界
//试探墙壁，避免越界
for(int i = 0; i <=6;i++){
s[0][i]=1;
s[i][0]=1;
s[6][i]=1;
s[i][6]=1;
}
整体代码
import java.util.Scanner;
public class test2 {
static int[][] s = new int[10][10];
static int[][] flag = new int[10][10];
static int min = 99;//初始化认为该路径很大
static int[] dx = {0, 1, 0, -1};//方向数组，顺时针：右 下 左 上
static int[] dy = {1, 0, -1, 0};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//试探墙壁，避免越界
for (int i = 0; i <= 6; i++) {
s[0][i] = 1;
s[i][0] = 1;
s[6][i] = 1;
s[i][6] = 1;
}
//将外围墙壁左上角顶点设置为（0，0）
for (int i = 1; i < 6; i++)//这里的从1开始，省去外围墙壁带来的不便
{
for (int j = 1; j < 6; j++) {
s[i][j] = sc.nextInt();
}
}
int sx = 1, sy = 1;//从（1，1）开始
flag[sx][sy] = 1;//进行标记
dfs(sx, sy, 0);//搜索
if (min == 99)//如果值还是原来的，就说明不存在
System.out.println("-1");
else
System.out.println(min);
}
public static void dfs(int x, int y, int step) {
if (x == 5 && y == 5) {//到达了右下角，终点
if (step < min) {//如果当前步数小于之前的
min = step;//标记更新
}
return;//否则返回空
}
for (int i = 0; i < 4; i++) {//控制方向数组
int xx = x + dx[i];//进行右，下，左，上搜索
int yy = y + dy[i];
if (flag[xx][yy] == 0 && s[xx][yy] == 0) {//如果未被标记，并且原来该位置的值为0
flag[xx][yy] = 1;//标记
dfs(xx, yy, step + 1);
flag[xx][yy] = 0;//回溯
}
}
}
}
加载全部内容