广度就是扩展开，广度优先的意思就是尽量扩展开。所以在算法实现的时候，就是一个循环遍历枚举每一个邻接点。其基本思路就是按层扩展，扩得越广越好。
伪代码如下：
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][4月22日是什么日子 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.hasht;import java.util.list;import java.util.t;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, t<integer> cache) { int m = a[0].length; int n = a.length; if (x < 0 || x >= m) { return fal; } if (y < 0 || y >= n) { return fal; } if (a[y][x].equals("0") && !cache.contains(x * 100000 + y)) { cache.add(x * 100000 + y); return true; } return fal; } 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; t<integer> cache = new hasht<>(); 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; }el { 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[] a野菜马齿苋rgs) { 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; t<integer> cache = new hasht<>(); 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.impty()) { 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实现广度优先遍历的示例详解的文章就介绍到这了,更多相关java广度优先遍历内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！
本文发布于:2023-04-04 21:18:35，感谢您对本站的认可！
本文链接：https://www.wtabcd.cn/fanwen/zuowen/4cc3b2221dfd29a090fddc6c4faa0d37.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
本文word下载地址：Java实现广度优先遍历的示例详解.doc
本文 PDF 下载地址：Java实现广度优先遍历的示例详解.pdf
| 留言与评论（共有 0 条评论） |
