溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
今天小編給大家分享一下Java中怎么實現廣度優先遍歷的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。
廣度就是擴展開，廣度優先的意思就是盡量擴展開。所以在算法實現的時候，就是一個循環遍歷枚舉每一個鄰接點。其基本思路就是按層擴展，擴得越廣越好。
偽代碼如下：
for(int i = 0; i < children.size(); i++){
children.get(i); // 調用每一個子節點
}我們以一個簡單的迷宮為例，以1代表墻，0代表路徑，我們構造一個具有出入口的迷宮。
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
以上面這個0為入口，下面這個0為出口，那么廣度優先的算法遍歷順序就為：dp[0][2]為入口，擴展出dp[1][2]，繼續擴展出dp[1][1]和dp[1][3]，我把這個過程列在下面了：
第一步：
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] ->到達終點
算法結束
好了，如果你已經懂了，就趕快去寫代碼吧。你可以使用一個二維數組來構建這個迷宮，然后思考怎么實現狀態流轉。
要實現一個簡單例子中的程序，我們需要編寫輸入函數，處理迷宮為01字符數組，然后編寫bfs函數作為主體函數，然后我們怎么讓代碼表現出行走狀態呢？假定當前坐標為 x,y，要行走，本質上就是判斷 (x-1,y) (x+1,y) (x,y+1) (x,y-1) 是否可以走，所以我們需要編寫一個判定函數，用來驗證邊界條件，這也是bfs里面的核心函數之一。以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) {
// 規定入口在第一行，出口在最后一行
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 根據現在的坐標，上下左右走
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 ? "不可達" : "可達，最短距離為" + ans+"步");
}
public static void main(String[] args) {
demo();
}
}這是數組的寫法，這也是這個簡單場景的寫法。不過在我們的實際生活中，更多的會使用隊列來實現廣度優先搜索。隊列模式下廣度優先搜索的偽代碼如下：
queue a;
while(!a.empty()){
a.take();
處理
將擴展出來的結果入隊
}那么上面這個迷宮，我們就可以使用標準廣度優先模板來實現，具體代碼如下：
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 根據現在的坐標，上下左右走
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函數。將上面的代碼合并到一起，執行的結果為：
可見，兩段代碼的結果是一致的。
以上就是“Java中怎么實現廣度優先遍歷”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
