Java实现广度优先遍历的示例详解

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，要行走，本质上就是判断http:// (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 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 = -http://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 cache = new HashSet<>();

cache.add(rux * 100000 + ruy);

List nexts = new ArrayList<>();

nexts.add(rux * 100000 + ruy);

while (true) {

if (nexts.size() == 0) {

ans = -1;

break;

}

int flag = 0;

List 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,http:// 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 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 cache = new HashSet<>();

cache.add(rux * 100000 + ruy);

queue.add(rux * 100000 + ruy);

Map 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函数。将上面的代码合并到一起，执行的结果为：

可见，两段代码的结果是一致的。

总结

简单总结一下，广度优先算法实现的时候主要需要解决两个问题。即，如何扩展（行走），临界判断。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。