Java实现深度搜索DFS算法详解

Java实现深度搜索DFS算法详解

目录DFS概述解释思路案例题-单身的蒙蒙题目描述题解整体代码

DFS概述

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。

解释

思路

一般用矩阵表示，从当前点开始，依次向周围四个方向试探，在我们给定数值条件下依次搜索（1代表不能走，0代表能走），对走过的路进行标记，如果最终达到了要走的点，就会进行回溯，回溯时，会将已经走过的点再次标记为未走，回到出发点，进行别的方向的试探

当找到距离最短的，而且到达了终点时，停止访问，输出结果

http://

案例题-单身的蒙蒙

题目描述

蒙蒙要找对象啦！但是对象在和他玩捉迷藏，现在有一个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 = xcBeHPP + 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;//回溯

}

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。