Java搜索與圖論之DFS和BFS算法詳解

更新時(shí)間：2022年11月22日 11:21:51 作者：秋落雨微涼

DFS指在進(jìn)行算法運(yùn)算時(shí)，優(yōu)先將該路徑的當(dāng)前路徑執(zhí)行完畢，執(zhí)行完畢或失敗后向上回溯嘗試其他途徑。BFS指在進(jìn)行算法運(yùn)算時(shí)，優(yōu)先將當(dāng)前路徑點(diǎn)的所有情況羅列出來，然后根據(jù)羅列出來的情況羅列下一層。本文介紹了二者的實(shí)現(xiàn)與應(yīng)用，需要的可以參考一下

DFS和BFS簡介

首先我們先來介紹一下DFS和BFS：

DFS：深度優(yōu)先遍歷算法，我們在進(jìn)行算法運(yùn)算時(shí)，優(yōu)先將該路徑的當(dāng)前路徑執(zhí)行完畢，執(zhí)行完畢或失敗后向上回溯嘗試其他途徑
BFS：廣度優(yōu)先遍歷算法，我們在進(jìn)行算法運(yùn)算時(shí)，優(yōu)先將當(dāng)前路徑點(diǎn)的所有情況羅列出來，然后根據(jù)羅列出來的情況羅列下一層

DFS和BFS的算法依據(jù)：

兩者均以樹的形式進(jìn)行展開，可以采用樹的模型來進(jìn)行DFS和BFS演示

DFS數(shù)字排序

我們首先給出DFS的一元問題：

給定一個(gè)整數(shù)n,將數(shù)字1∼n排成一排，將會(huì)有很多種排列方法。
現(xiàn)在，請你按照字典序?qū)⑺械呐帕蟹椒ㄝ敵觥?/li>

問題解析：

一元問題解析

我們目前采用DFS算法運(yùn)算，我們需要一次得到數(shù)據(jù)，然后回溯

那么我們目前的問題就是：

如何判斷DFS算法結(jié)束：我們只需要記錄遍歷到第幾個(gè)數(shù)字然后與之判斷是否相等，若相等表示結(jié)束
如何得知當(dāng)前數(shù)字已經(jīng)使用：我們只需要單列一個(gè)數(shù)組來記錄該數(shù)是否被使用即可

我們給出算法代碼：

import java.util.Scanner;

public class Main {

    public static final int N = 10;

    // 存放數(shù)據(jù)
    static int n;
    static int[] arr = new int[N];
    static int[] res = new int[N];

    // 判斷是否被使用
    static boolean[] isUsed = new boolean[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        for (int i = 0; i < n; i++) {
            arr[i] = i+1;
        }

        dfs(0);
    }

    public static void dfs(int x){
        // 首先判斷是否可以輸出
        if (x == n){
            for (int i=0;i < n;i++){
                System.out.print(res[i]+ " ");
            }
            System.out.println();
        }

        // 開始dfs
        for (int i = 0; i < n; i++) {
            // 判斷是否被使用，若被使用，則不能使用；若未被使用，使用并進(jìn)入下一層
            if (!isUsed[i]){
                // 未被使用，使用并進(jìn)入下一層
                res[x] = arr[i];
                isUsed[i] = true;
                dfs(x+1);
                // 下面屬于回溯部分，我們需要恢復(fù)原樣，這里的x已經(jīng)回溯，不需要覆蓋res的值
                isUsed[i] = false;
            }
        }
    }
}

DFS皇后排序

我們首先給出DFS的二元問題：

n−皇后問題是指將n個(gè)皇后放在n×n的國際象棋棋盤上，使得皇后不能相互攻擊到
即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。
現(xiàn)在給定整數(shù) nn，請你輸出所有的滿足條件的棋子擺法。

問題解析：

原始方法

首先我們采用最基本的思想，我們采用一元思想，針對(duì)n*n的棋盤上的每個(gè)位置都進(jìn)行DFS操作，并對(duì)其判斷是否滿足條件

在滿足條件的位置上我們放上皇后并記錄數(shù)目，如果到最后皇后的數(shù)量足夠，那么我們就將他輸出

升級(jí)方法

我們已經(jīng)知道他們不能放在同一行和同一列，我們直接采用for將一行中的一個(gè)位置選出來，然后對(duì)每行DFS操作并判斷是否滿足條件

在滿足條件的位置上我們放上皇后并記錄數(shù)目，如果到最后皇后的數(shù)量足夠，那么我們就將他輸出

注意點(diǎn)

我們的n-皇后問題還需要保證對(duì)角線上不具有相同棋子

我們采用二元函數(shù)的函數(shù)y=x以及y=n-x來給出對(duì)角線的位置

我們給出算法代碼：

/*原始方法*/

import java.util.Scanner;

public class dfsDouble {

    static final int N = 20;

    // 記錄數(shù)據(jù)
    static int n;
    static char[][] arr = new char[N][N];

    // 記錄行，列，對(duì)角線，反對(duì)角線
    static boolean[] row = new boolean[N];
    static boolean[] col = new boolean[N];
    static boolean[] dg = new boolean[2*N-1];
    static boolean[] udg = new boolean[2*N-1];

    // 主函數(shù)
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        for (int i = 0;i < n;i++){
            for (int j = 0; j < n; j++) {
                arr[i][j] = '.';
            }
        }

        dfs(0,0,0);

    }

    // DFS
    private static void dfs(int x,int y,int u) {

        // y到頭，換行
        if(y == n){
            y = 0;
            x++;
        }

        // 老規(guī)矩判斷輸出條件
        if (x == n){
            if (u == n){
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        System.out.print(arr[i][j]);
                    }
                    System.out.println();
                }
                System.out.println();
            }
            return;
        }

        // 進(jìn)行dfs（不選的情況，選該行的其他點(diǎn)位）
        dfs(x, y + 1, u);

        // 判斷是否符合條件
        if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
        {
            arr[x][y] = 'Q';
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;

            // 進(jìn)行dfs(符合條件選，繼續(xù)下一步)
            dfs(x, y + 1, u + 1);

            row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
            arr[x][y] = '.';
        }
    }
}

/*升級(jí)方法*/

import java.util.Scanner;

public class dfsDouble {

    static final int N = 20;

    // 記錄數(shù)據(jù)
    static int n;
    static char[][] arr = new char[N][N];

    // 記錄列，對(duì)角線，反對(duì)角線
    static boolean[] col = new boolean[N];
    static boolean[] dg = new boolean[2*N-1];
    static boolean[] udg = new boolean[2*N-1];

    // 主函數(shù)
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        for (int i = 0;i < n;i++){
            for (int j = 0; j < n; j++) {
                arr[i][j] = '.';
            }
        }

        dfs(0);

    }

    // DFS
    private static void dfs(int u) {

        // 我們采用每行取一個(gè)的策略，這里的u就是x
        if (u == n){
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(arr[i][j]);
                }
                System.out.println();
            }
            System.out.println();
            return;
        }

        // 我們?nèi)M足條件的位置
        for (int j = 0; j < n; j++) {
            if (!col[j] && !dg[u+j] && !udg[u - j + n]){
                arr[u][j] = 'Q';
                col[j] = dg[u+j] = udg[u-j+n] = true;
                dfs(u+1);
                col[j] = dg[u+j] = udg[u-j+n] = false;
                arr[u][j] = '.';
            }
        }
    }
}

DFS樹的重心

我們這里利用DFS來求解一道難題：

給定一顆樹，樹中包含 nn 個(gè)結(jié)點(diǎn)（編號(hào) 1∼n1∼n）和 n−1n−1 條無向邊。
請你找到樹的重心，并輸出將重心刪除后，剩余各個(gè)連通塊中點(diǎn)數(shù)的最大值。
重心定義：重心是指樹中的一個(gè)結(jié)點(diǎn)，如果將這個(gè)點(diǎn)刪除后，剩余各個(gè)連通塊中點(diǎn)數(shù)的最大值最小，那么這個(gè)節(jié)點(diǎn)被稱為樹的重心。

我們給出一個(gè)簡單示例來表明重心：

我們來簡單介紹一下：

輸入數(shù)據(jù)

第一個(gè)是操作次數(shù)，然后后面成對(duì)書寫，表示兩者相連

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

重心介紹

我們上圖中的黑筆書寫部分是由上述數(shù)據(jù)所搭建出來的無向圖，我們上面用樹的形式寫出

我們的棕筆部分是指去掉該點(diǎn)之后，剩余的聯(lián)通點(diǎn)分塊的個(gè)數(shù)中的最大塊，我們要測試全部的點(diǎn)位，并給出這些最大塊的最小快

思路分析

首先我們要遍歷所有的點(diǎn)，一一求解該點(diǎn)刪除后的最大塊

我們刪除該點(diǎn)后，其連通區(qū)域主要分為兩部分：該點(diǎn)的子點(diǎn)，該點(diǎn)的上一個(gè)點(diǎn)的個(gè)數(shù)去除該點(diǎn)以及該點(diǎn)子類的個(gè)數(shù)

我們給出相關(guān)代碼：

import java.util.Scanner;

public class Main {

    final static int N = 100010;

    // 首先我們用單鏈表模擬圖
    static int n;
    static int idx;
    static int[] h = new int[N];
    static int[] e = new int[N*2];
    static int[] ne = new int[N*2];

    // 判定是否已經(jīng)經(jīng)過
    static boolean[] isPassed = new boolean[N*2];

    // 最大值
    static int ans = N;


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        // 將頭節(jié)點(diǎn)設(shè)為-1，方便判斷
        for (int i = 1; i < N; i++) {
            h[i] = -1;
        }

        // 進(jìn)行連接
        for (int i = 0; i < n-1; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            // 注意是無向邊，我們需要雙向連接
            add(a,b);
            add(b,a);
        }

        // 開始遍歷
        dfsMethod(1);

        // 最后輸出結(jié)果
        System.out.println(ans);
    }

    // dfs操作
    private static int dfsMethod(int u) {

        // 連通塊的最大值
        int res = 0;

        // 首先將自己設(shè)置為已經(jīng)過點(diǎn)
        isPassed[u] = true;

        // 該點(diǎn)以及子類的點(diǎn)數(shù)(目前已包含自己點(diǎn))
        int sum = 1;

        // 開始遍歷子點(diǎn)
        for (int i = h[u];i != -1;i = ne[i]){

            // 將每個(gè)點(diǎn)用變量表示出來
            int j = e[i];

            // 如果該點(diǎn)沒有經(jīng)過,對(duì)其dfs遍歷
            if (!isPassed[j]){
                // 遍歷時(shí)需要返回sum來獲得下列點(diǎn)的大小，為了得到ans做準(zhǔn)備
                int s = dfsMethod(j);

                // 和res比較，獲得連通塊最大值
                res = Math.max(res,s);

                // 將子類點(diǎn)添加到sum中
                sum += s;
            }
        }


        // 我們還需要與拋棄該點(diǎn)后上面的點(diǎn)所產(chǎn)生的res作比較
        res = Math.max(res,n-sum);

        // 返回最小的ans
        ans = Math.min(ans,res);

        return sum;

    }

    // 我們需要一個(gè)單鏈表連接的函數(shù)
    public static void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}

BFS走迷宮

我們給出BFS走迷宮題目：

給定一個(gè)n×m的二維整數(shù)數(shù)組，用來表示一個(gè)迷宮，數(shù)組中只包含0或1，其中0表示可以走的路，1表示不可通過的墻壁。
最初，有一個(gè)人位于左上角 (1,1)處，已知該人每次可以向上、下、左、右任意一個(gè)方向移動(dòng)一個(gè)位置。
請問，該人從左上角移動(dòng)至右下角 (n,m)處，至少需要移動(dòng)多少次。
數(shù)據(jù)保證 (1,1)處和 (n,m)處的數(shù)字為0，且一定至少存在一條通路。

問題解析：

BFS運(yùn)作

首先我們要知道BFS的運(yùn)作形式
首先我們BFS是根據(jù)距離或長度來進(jìn)行分類遞增
那么在走迷宮時(shí)，我們距離為n+1的位置肯定是由距離為n的位置的上下左右方向的位置
那么我們就可以采用一個(gè)隊(duì)列來進(jìn)行裝配，我們將獲得的可走的點(diǎn)位和距離保存進(jìn)去，然后根據(jù)這個(gè)點(diǎn)位和距離推算下一個(gè)點(diǎn)位和距離

我們給出算法代碼：

import java.util.Scanner;

public class bfs {

    static final int N = 100;

    // 存放數(shù)據(jù)，存放是否使用
    static int n,m,hh,tt;
    static int[][] arr = new int[N][N];// 地圖
    static int[][] isPassed = new int[N][N];// 是否經(jīng)過,若經(jīng)過修改為距離
    static PII[] queue = new PII[N*N];// 隊(duì)列

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        m = scanner.nextInt();

        for (int i=1;i <= n;i++){
            for (int j=1;j <= m;j++){
                // 輸入0/1
                arr[i][j] = scanner.nextInt();
                // 全部設(shè)置為未pass
                isPassed[i][j] = -1;
            }
        }

        int res = bfsMethod();
        System.out.println(res);
    }

    private static int bfsMethod() {

        // 初始設(shè)置
        hh = 0 ; tt = -1; //隊(duì)列的頭節(jié)點(diǎn)=0，尾節(jié)點(diǎn) = 0；
        isPassed[1][1] = 0; // 我們首先站在的是第一個(gè)點(diǎn)，所以值距離設(shè)置為0
        queue[++tt] = new PII(1,1); //然后將第一個(gè)點(diǎn)下標(biāo)存入q隊(duì)列中

        // 提前設(shè)置好移動(dòng)方向(分別對(duì)應(yīng)方向)
        int[] xmove = {-1,0,1,0};
        int[] ymove = {0,1,0,-1};

        // 遍歷queue
        while (hh <= tt){
                PII t = queue[hh++]; //每一次將頭結(jié)點(diǎn)拿出來
                for(int i = 0 ; i < 4 ; i ++ ) {//然后進(jìn)行下一步要往哪里走，這里可能有多重選擇可走
                    int x = t.x + xmove[i]; //這里進(jìn)行x軸向量判斷
                    int y = t.y + ymove[i];//這里進(jìn)行y軸向量的判斷
                    //如果x，y滿足在地圖中不會(huì)越界，然后地圖上的點(diǎn)g是0(表示可以走)，
                    //然后這里是沒走過的距離d是-1；
                    if (x > 0 && x <= n && y > 0 && y <= m && arr[x][y] == 0 && isPassed[x][y] == -1) {
                        //將現(xiàn)在可以走的點(diǎn)(x,y)加上上一個(gè)點(diǎn)計(jì)數(shù)距離的點(diǎn)加上一，就是現(xiàn)在走到的點(diǎn)的距離
                        isPassed[x][y] = isPassed[t.x][t.y] + 1;
                        queue[++tt] = new PII(x, y);//然后將這一個(gè)可以走的點(diǎn)存入隊(duì)列尾
                    }
                }
        }
        return isPassed[n][m]; //最后返回的是地圖走到盡頭最后一個(gè)位置的位置統(tǒng)計(jì)的距離
    }

    //這是一個(gè)用來存儲(chǔ)兩個(gè)坐標(biāo)的類Pair
    static class PII{
        int x,y;
        public PII(int x,int y){
            this.x  = x;
            this.y = y;
        }
    }
}

BFS八數(shù)碼

我們給出BFS八數(shù)碼題目：

在一個(gè)3×3的網(wǎng)格中，1∼8這 88 個(gè)數(shù)字和一個(gè) x 恰好不重不漏地分布在這 3×3的網(wǎng)格中。
在游戲過程中，可以把 x 與其上、下、左、右四個(gè)方向之一的數(shù)字交換（如果存在）。

我們需要將八數(shù)碼從下列形式變成順序形式：

/*原八數(shù)碼*/

1 2 3
x 4 6
7 5 8
    
/*完善八數(shù)碼*/
    
1 2 3
4 5 6
7 8 x
    
/*變化順序*/
    
1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

問題解析：

八數(shù)碼問題解析

我們這里要計(jì)算最小的移動(dòng)步數(shù)，那么我們就需要采用BFS來計(jì)算最近的

其實(shí)和之前的走迷宮非常相似，我們將x與上下左右四個(gè)方向的數(shù)進(jìn)行對(duì)換，然后比較是否為最終結(jié)果即可

我們給出算法代碼：

import java.util.*;

public class bfs {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        // 開始狀況
        String start = "";

        for(int i = 0 ; i < 9 ; i ++ ){
            String s = scanner.next();
            start += s;
        }

        // 結(jié)束狀況
        String end = "12345678x";

        // bfs循環(huán)
        System.out.println(bfsMethod(start,end));
    }

    public static int bfsMethod(String start,String end){
        // 哈希表存放字符串和對(duì)應(yīng)的移動(dòng)步數(shù)
        HashMap<String,Integer> hashMap = new HashMap<String, Integer>();
        // 隊(duì)列存放字符串
        Queue<String> queue = new LinkedList<>();

        // 存放第一個(gè)點(diǎn)(還未開始，啟動(dòng)步數(shù)為0)
        hashMap.put(start,0);
        queue.add(start);

        while (!queue.isEmpty()){
            // 將head數(shù)據(jù)拿出來
            String s = queue.poll();

            // 首先判斷是否符合條件
            if (s.equals(end)) return hashMap.get(s);

            // 找到x坐標(biāo)
            int index = s.indexOf("x");

            // 計(jì)算對(duì)應(yīng)位置
            int x = index/3;
            int y = index%3;

            // 然后上下左右移動(dòng)判斷
            int[] xmove = {1,0,-1,0};
            int[] ymove = {0,1,0,-1};

            for (int i=0;i<4;i++){

                int a = x + xmove[i];
                int b = y + ymove[i];

                //如果這種情況沒有超出邊界
                if(a >= 0 && a < 3 && b >= 0 && b < 3){

                    //將這種情況的字符串轉(zhuǎn)化成字符數(shù)組，能夠有下標(biāo)進(jìn)行交換
                    char[] arr = s.toCharArray();

                    //然后交換x跟沒有超出邊界的值進(jìn)行交換，二維轉(zhuǎn)成一維下標(biāo)x*3+y;
                    swap(arr, index, a * 3 + b);

                    //然后將字符數(shù)組轉(zhuǎn)化成字符串
                    String str = new String(arr);

                    //如果這種情況對(duì)應(yīng)的value值是null，說明還沒有走過
                    if(hashMap.get(str) == null){

                        //然后將這種情況對(duì)應(yīng)進(jìn)行上一步的距離加上1
                        hashMap.put(str,hashMap.get(s) + 1);

                        //然后將新的情況插入到隊(duì)尾中
                        queue.offer(str);
                    }
                }
            }
        }
        return -1;
    }

    // 交換算法
    public static void swap(char[] arr,int x,int y){
        char temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}

BFS圖層次

我們這里利用BFS來求解一道難題：

給定一個(gè)n個(gè)點(diǎn)m條邊的有向圖，圖中可能存在重邊和自環(huán)。
所有邊的長度都是1，點(diǎn)的編號(hào)為1∼n。
請你求出1號(hào)點(diǎn)到n號(hào)點(diǎn)的最短距離，如果從1號(hào)點(diǎn)無法走到n號(hào)點(diǎn)，輸出 −1。

我們采用BFS來逐層遞進(jìn)，其原理其實(shí)和前面兩道題相同：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class bfsssss {

    final static int N = 100010;

    // 單鏈表模擬圖
    static int n,m;
    static int hh,tt;
    static int idx;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];

    // 距離存儲(chǔ)以及隊(duì)列
    static int[] distance = new int[N];
    static int[] queue = new int[N];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        // 初始化
        for (int i = 1; i < N; i++) {
            h[i] = -1;
            distance[i] = -1;
        }

        // 賦值
        for (int i = 0;i < m;i++ ){
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            add(a,b);
        }

        // BFS操作
        int res = bfsFind();

        // 輸出
        System.out.println(res);
    }

    // bfs操作
    public static int bfsFind(){

        // 設(shè)置hh，tt
        hh = 0;
        tt = -1;

        // 第一個(gè)點(diǎn)距離為0
        distance[1] = 0;

        // 將第一個(gè)點(diǎn)加入隊(duì)列
        queue[++tt] = 1;

        // 開始隊(duì)列循環(huán)
        while (hh <= tt){
            int t = queue[hh++];
            // 取得該點(diǎn)，對(duì)其ne進(jìn)行處理
            for (int i = h[t]; i != -1; i = ne[i]) {
                // 得到該子點(diǎn)，進(jìn)行處理
                int s = e[i];
                if (distance[s] == -1){
                    // 如果沒有經(jīng)過就設(shè)置dis,并且加入隊(duì)列
                    distance[s] = distance[t] + 1;
                    queue[++tt] = s;
                }
            }
        }
        return distance[n];
    }

    // 經(jīng)典單鏈表添加方法
    public static void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx;
        idx++;
    }
}

以上就是Java搜索與圖論之DFS和BFS算法詳解的詳細(xì)內(nèi)容，更多關(guān)于Java DFS BFS的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: