Java實現(xiàn)深度搜索DFS算法詳解

更新時間：2021年12月17日 10:45:40 作者：java舞動乾坤

深度優(yōu)先搜索是一種在開發(fā)爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點。這篇文章主要介紹了基于Java實現(xiàn)深度優(yōu)先搜索（DFS）算法，需要的朋友可以參考一下

DFS概述

深度優(yōu)先搜索是一種在開發(fā)爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件) 。在一個HTML文件中，當一個超鏈被選擇后，被鏈接的HTML文件將執(zhí)行深度優(yōu)先搜索，即在搜索其余的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優(yōu)先搜索沿著HTML文件上的超鏈走到不能再深入為止，然后返回到某一個HTML文件，再繼續(xù)選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經(jīng)結束。

解釋

思路

一般用矩陣表示，從當前點開始，依次向周圍四個方向試探，在我們給定數(shù)值條件下依次搜索（1代表不能走，0代表能走），對走過的路進行標記，如果最終達到了要走的點，就會進行回溯，回溯時，會將已經(jīng)走過的點再次標記為未走，回到出發(fā)點，進行別的方向的試探

當找到距離最短的，而且到達了終點時，停止訪問，輸出結果

案例題-單身的蒙蒙

題目描述

蒙蒙要找對象啦！但是對象在和他玩捉迷藏，現(xiàn)在有一個55的地圖，蒙蒙就在（0，0）的位置，他的心上人就在（4，4）的位置，當然路上會有各種艱難險阻，現(xiàn)在說明一下規(guī)則。蒙蒙按照地圖行動，一次走一步，而且他只能前后左右的移動，當然蒙蒙也不能穿越墻壁。地圖上有兩種圖案，一種是‘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

題解

分析: 首先分析下，主人公要想能夠找到對象，就需要走到左下角，而去的過程顯然不是一帆風順的，它會遇到墻壁，遇到墻壁就會返回，返回到前一個點之后向其他方向進行搜索，如果有通路，就會接著執(zhí)行這步的操作，直到找到終點。題目中問的是最少要通過多少步才能找到對象，那么顯然可能一次搜索找不到最短的路徑，這里就需要回溯，把回溯的點設置為未標記，回溯到最初的點之后進行其他方向的遍歷，如果第二次到達終點的值小于第一次的就更新路徑，將第二次的路徑作為最小的路徑，直到所有點遍歷完

//回溯算法
flag[xx][yy]=1//標記
dfs(1,1,step+1)
//flag[xx][yy]=0;設置為未標記的點，進行回溯

方向數(shù)組因為要進行四個方向的試探，所以要定義一個方向數(shù)組：方向數(shù)組的定義可以使用一維數(shù)組，亦可以使用二維數(shù)組，建議大家使用一維數(shù)組，直觀明了，這里解釋下便于方便，將標準坐標軸順時針方向旋轉(zhuǎn)了90度，令x=0;y=0則可有四個方向坐標右：（0，1），下：（1，0），左：（0，-1），上：（-1，0），依次取dx一次，dy一次，就和上面的坐標一致了

    static int[] dx = {0, 1, 0, -1};//方向數(shù)組，順時針：右 下 左 上
    static int[] dy = {1, 0, -1, 0};

注意事項: 這里因為輸入的是從原點開始，而外界臨界值也是等同于墻壁，為了免去試探，可以將四邊的設置為“1”墻壁，這樣可以避免數(shù)組越界

 //試探墻壁，避免越界
        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};//方向數(shù)組，順時針：右 下 左 上
    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) {//如果當前步數(shù)小于之前的
                min = step;//標記更新
            }
            return;//否則返回空
        }
        for (int i = 0; i < 4; i++) {//控制方向數(shù)組
            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;//回溯
            }
        }

    }
}

到此這篇關于Java實現(xiàn)深度搜索DFS算法詳解的文章就介紹到這了,更多相關Java 深度搜索DFS算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: