DFS概述

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

解釋

思路

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

當(dāng)找到距離最短的，而且到達(dá)了終點(diǎn)時(shí)，停止訪問，輸出結(jié)果

案例題-單身的蒙蒙

題目描述

蒙蒙要找對象啦！但是對象在和他玩捉迷藏，現(xiàn)在有一個(gè)55的地圖，蒙蒙就在（0，0）的位置，他的心上人就在（4，4）的位置，當(dāng)然路上會(huì)有各種艱難險(xiǎn)阻，現(xiàn)在說明一下規(guī)則。蒙蒙按照地圖行動(dòng)，一次走一步，而且他只能前后左右的移動(dòng)，當(dāng)然蒙蒙也不能穿越墻壁。地圖上有兩種圖案，一種是‘0'表示可以走的路，另一種是‘1'表示不能走的墻

PS:（0，0）就是左上角，（4，4）就是右下角，都懂吧！

輸入：

輸入一個(gè)55的矩陣表示地圖，‘0'表示可以走的路，‘1'表示不能走的墻，蒙蒙就在（0，0）的位置，他的心上人就在（4，4）的位置

輸出：

輸出蒙蒙到心上人那里最少要走多少步，若蒙蒙永遠(yuǎn)走不到心上人那里，則輸出-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

題解

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

//回溯算法
flag[xx][yy]=1//標(biāo)記
dfs(1,1,step+1)
//flag[xx][yy]=0;設(shè)置為未標(biāo)記的點(diǎn)，進(jìn)行回溯

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

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

注意事項(xiàng): 這里因?yàn)檩斎氲氖菑脑c(diǎn)開始，而外界臨界值也是等同于墻壁，為了免去試探，可以將四邊的設(shè)置為“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;//初始化認(rèn)為該路徑很大
    static int[] dx = {0, 1, 0, -1};//方向數(shù)組，順時(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;
        }
        //將外圍墻壁左上角頂點(diǎn)設(shè)置為（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;//進(jìn)行標(biāo)記
        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) {//到達(dá)了右下角，終點(diǎn)
            if (step < min) {//如果當(dāng)前步數(shù)小于之前的
                min = step;//標(biāo)記更新
            }
            return;//否則返回空
        }
        for (int i = 0; i < 4; i++) {//控制方向數(shù)組
            int xx = x + dx[i];//進(jìn)行右，下，左，上搜索
            int yy = y + dy[i];
            if (flag[xx][yy] == 0 && s[xx][yy] == 0) {//如果未被標(biāo)記，并且原來該位置的值為0
                flag[xx][yy] = 1;//標(biāo)記
                dfs(xx, yy, step + 1);
                flag[xx][yy] = 0;//回溯
            }
        }

    }
} 

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

最新評(píng)論