Java實(shí)現(xiàn)廣度優(yōu)先遍歷的示例詳解

更新時(shí)間：2022年02月01日 08:32:34 作者：炒雞辣雞123

廣度優(yōu)先遍歷：廣度優(yōu)先遍歷是連通圖的一種遍歷策略，因?yàn)樗乃枷胧菑囊粋€(gè)頂點(diǎn)V0開始，輻射狀地優(yōu)先遍歷其周圍較廣的區(qū)域故得名。本文詳細(xì)介紹了Java如何實(shí)現(xiàn)廣度優(yōu)先遍歷，感興趣的小伙伴可以學(xué)習(xí)一下

什么是廣度優(yōu)先

廣度就是擴(kuò)展開，廣度優(yōu)先的意思就是盡量擴(kuò)展開。所以在算法實(shí)現(xiàn)的時(shí)候，就是一個(gè)循環(huán)遍歷枚舉每一個(gè)鄰接點(diǎn)。其基本思路就是按層擴(kuò)展，擴(kuò)得越廣越好。

偽代碼如下：

for(int i = 0; i < children.size(); i++){
    children.get(i); // 調(diào)用每一個(gè)子節(jié)點(diǎn)
}

一個(gè)簡單的例子

我們以一個(gè)簡單的迷宮為例，以1代表墻，0代表路徑，我們構(gòu)造一個(gè)具有出入口的迷宮。

1 1 0 1 1 1 1 1 1

1 0 0 0 0 0 0 1 1

1 0 1 1 1 1 0 1 1

1 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 0 1

以上面這個(gè)0為入口，下面這個(gè)0為出口，那么廣度優(yōu)先的算法遍歷順序就為：dp[0][2]為入口，擴(kuò)展出dp[1][2]，繼續(xù)擴(kuò)展出dp[1][1]和dp[1][3]，我把這個(gè)過程列在下面了：

第一步：

dp[0][2] -> dp[1][2]

第二步：

dp[1][2] -> dp[1][1] & dp[1][3]

第三步：

dp[1][1] -> dp[2][1]

dp[1][3] -> dp[1][4]

第四步：

dp[2][1] -> dp[3][1]

dp[1][4] -> dp[1][5]

第五步：

dp[3][1] -> dp[3][2]

dp[1][5] -> dp[1][6]

第六步：

dp[3][2] -> dp[3][3]

dp[1][6] -> dp[2][6]

第七步：

dp[3][3] -> dp[3][4]

dp[2][6] -> dp[3][6]

第八步：

dp[3][4] -> dp[3][5]

dp[3][6] -> dp[3][7]

第九步：

dp[3][5] -> dp[3][6]

dp[3][7] -> dp[4][7] ->到達(dá)終點(diǎn)

算法結(jié)束

好了，如果你已經(jīng)懂了，就趕快去寫代碼吧。你可以使用一個(gè)二維數(shù)組來構(gòu)建這個(gè)迷宮，然后思考怎么實(shí)現(xiàn)狀態(tài)流轉(zhuǎn)。

程序?qū)崿F(xiàn)

要實(shí)現(xiàn)一個(gè)簡單例子中的程序，我們需要編寫輸入函數(shù)，處理迷宮為01字符數(shù)組，然后編寫bfs函數(shù)作為主體函數(shù)，然后我們怎么讓代碼表現(xiàn)出行走狀態(tài)呢？假定當(dāng)前坐標(biāo)為 x,y，要行走，本質(zhì)上就是判斷 (x-1,y) (x+1,y) (x,y+1) (x,y-1) 是否可以走，所以我們需要編寫一個(gè)判定函數(shù)，用來驗(yàn)證邊界條件，這也是bfs里面的核心函數(shù)之一。以Java代碼為例

package com.chaojilaji.book;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Bfs {

    public static String[][] getInput(String a) {
        String[] b = a.split("\n");
        int n = 0, m = 0;
        m = b.length;
        for (int i = 0; i < b.length; i++) {
            String[] c = b[i].split("  ");
            n = c.length;
            break;
        }
        String[][] x = new String[m][n];
        for (int i = 0; i < b.length; i++) {
            String[] c = b[i].split("  ");
            for (int j = 0; j < c.length; j++) {
                x[i][j] = c[j];
            }
        }
        return x;
    }

    public static Boolean canAdd(String[][] a, Integer x, Integer y, Set<Integer> cache) {
        int m = a[0].length;
        int n = a.length;
        if (x < 0 || x >= m) {
            return false;
        }
        if (y < 0 || y >= n) {
            return false;
        }
        if (a[y][x].equals("0") && !cache.contains(x * 100000 + y)) {
            cache.add(x * 100000 + y);
            return true;
        }
        return false;
    }

    public static Integer bfs(String[][] a) {
        // 規(guī)定入口在第一行，出口在最后一行
        int m = a[0].length;
        int n = a.length;
        int rux = -1, ruy = 0;
        int chux = -1, chuy = n - 1;
        for (int i = 0; i < m; i++) {
            if (a[0][i].equals("0")) {
                // TODO: 2022/1/11 找到入口
                rux = i;
            }
            if (a[n - 1][i].equals("0")) {
                chux = i;
            }
        }
        Integer ans = 0;
        Set<Integer> cache = new HashSet<>();
        cache.add(rux * 100000 + ruy);
        List<Integer> nexts = new ArrayList<>();
        nexts.add(rux * 100000 + ruy);
        while (true) {
            if (nexts.size() == 0) {
                ans = -1;
                break;
            }
            int flag = 0;
            List<Integer> tmpNexts = new ArrayList<>();
            for (Integer next : nexts) {
                int x = next / 100000;
                int y = next % 100000;
                if (x == chux && y == chuy) {
                    flag = 1;
                    break;
                }
                // TODO: 2022/1/11 根據(jù)現(xiàn)在的坐標(biāo)，上下左右走
                if (canAdd(a, x - 1, y, cache)) tmpNexts.add((x - 1) * 100000 + y);
                if (canAdd(a, x + 1, y, cache)) tmpNexts.add((x + 1) * 100000 + y);
                if (canAdd(a, x, y - 1, cache)) tmpNexts.add(x * 100000 + (y - 1));
                if (canAdd(a, x, y + 1, cache)) tmpNexts.add(x * 100000 + (y + 1));
            }
            nexts.clear();
            nexts.addAll(tmpNexts);
            if (flag == 1) {
                break;
            }else {
                ans++;
            }
        }
        return ans;
    }

    public static void demo() {
        String a = "1  1  0  1  1  1  1  1  1\n" +
                "1  0  0  0  0  0  0  1  1\n" +
                "1  0  1  1  1  1  0  1  1\n" +
                "1  0  0  0  0  0  0  0  1\n" +
                "1  1  1  1  1  1  1  0  1";
        String[][] b = getInput(a);

        Integer ans = bfs(b);
        System.out.println(ans == -1 ? "不可達(dá)" : "可達(dá)，最短距離為" + ans+"步");
    }

    public static void main(String[] args) {
        demo();
    }
}

這是數(shù)組的寫法，這也是這個(gè)簡單場景的寫法。不過在我們的實(shí)際生活中，更多的會使用隊(duì)列來實(shí)現(xiàn)廣度優(yōu)先搜索。隊(duì)列模式下廣度優(yōu)先搜索的偽代碼如下：

queue a;
while(!a.empty()){
	a.take();
    處理
    將擴(kuò)展出來的結(jié)果入隊(duì)
}

那么上面這個(gè)迷宮，我們就可以使用標(biāo)準(zhǔn)廣度優(yōu)先模板來實(shí)現(xiàn)，具體代碼如下：

public static Integer bfsQueue(String[][] a) {
        Queue<Integer> queue = new LinkedList<>();
        int m = a[0].length;
        int n = a.length;
        int rux = -1, ruy = 0;
        int chux = -1, chuy = n - 1;
        for (int i = 0; i < m; i++) {
            if (a[0][i].equals("0")) {
                // TODO: 2022/1/11 找到入口
                rux = i;
            }
            if (a[n - 1][i].equals("0")) {
                chux = i;
            }
        }
        Integer ans = 0;
        Set<Integer> cache = new HashSet<>();
        cache.add(rux * 100000 + ruy);
        queue.add(rux * 100000 + ruy);
        Map<Integer, Integer> buzi = new HashMap<>();
        buzi.put(rux * 100000 + ruy, 0);
        int flag = 0;
        while (!queue.isEmpty()) {
            Integer val = queue.poll();
            int x = val / 100000;
            int y = val % 100000;
            if (x == chux && y == chuy) {
                flag = 1;
                ans = buzi.get(x * 100000 + y);
                break;
            }
            // TODO: 2022/1/11 根據(jù)現(xiàn)在的坐標(biāo)，上下左右走
            if (canAdd(a, x - 1, y, cache)) {
                buzi.put((x - 1) * 100000 + y, buzi.get(x * 100000 + y)+1);
                queue.add((x - 1) * 100000 + y);
            }
            if (canAdd(a, x + 1, y, cache)) {
                buzi.put((x + 1) * 100000 + y, buzi.get(x * 100000 + y)+1);
                queue.add((x + 1) * 100000 + y);
            }
            if (canAdd(a, x, y - 1, cache)) {
                buzi.put(x * 100000 + (y - 1), buzi.get(x * 100000 + y)+1);
                queue.add(x * 100000 + (y - 1));
            }
            if (canAdd(a, x, y + 1, cache)) {
                buzi.put(x * 100000 + y + 1, buzi.get(x * 100000 + y)+1);
                queue.add(x * 100000 + (y + 1));
            }
        }
        if (flag == 1){
            return ans;
        }
        return -1;
    }

這段代碼就可以替換掉上一段代碼中的bfs函數(shù)。將上面的代碼合并到一起，執(zhí)行的結(jié)果為：