Shulou(Shulou.com)06/01 Report--

Today, the editor will share with you the relevant knowledge points about how to achieve breadth-first traversal in Java. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article.

What is breadth first?

Breadth means to expand, and breadth first means to expand as much as possible. So when the algorithm is implemented, it is a loop to enumerate each adjacent point. The basic idea is to expand by layer, the wider the better.

The pseudo code is as follows:

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]

Step 2:

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

Step 3:

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

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

Step 4:

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

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

Step 5:

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

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

Step 6:

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

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

Step 7:

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

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

Step 8:

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

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

Step 9:

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

Dp [3] [7]-> dp [4] [7]-> reach the destination

Algorithm end

Well, if you already understand, go ahead and write the code. You can use a two-dimensional array to build the maze and think about how to achieve state transfer.

Program realization

To implement the program in a simple example, we need to write an input function, deal with the maze as an array of 01 characters, and then write the bfs function as the body function, and then how do we make the code walk? Assuming that the current coordinate is xmemy, to walk is essentially to judge whether (xmem1maginy) (xmemyphil1) (xmemymer1) (xmemymer1) can go, so we need to write a decision function to verify the boundary conditions, which is also one of the core functions in bfs. Take Java code as an example

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.resume; 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) {/ / specifies that the entrance is on the first line and the exit is on the last line 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); 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, 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函数。将上面的代码合并到一起，执行的结果为：

It can be seen that the results of the two pieces of code are consistent.

These are all the contents of the article "how to achieve breadth-first traversal in Java". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.