Java 广度优先遍历 (BFS) 在使用JAVA的二维数组上

介绍

广度优先遍历 (BFS) 是一种图遍历技术，它从源单元格开始，向外逐层移动，以达到二维数组中的所有节点。它按照节点距离源节点的顺序访问节点，从最近的节点开始，并逐步向外扩散。在无权图中，BFS保证从源节点到每个可达单元格都存在最短路径。

要成功地将BFS应用于二维数组，有必要对什么是二维数组有一个深入的理解。在计算机科学中，网格、地图或迷宫可以表示为二维数组，即类似矩阵的数据结构，具有行和列。了解如何在行和列之间索引和检索数据对于有效实现至关重要。

对二维数组上BFS的逐步解释

广度优先遍历 (BFS) 是一种用于访问和探索图中的所有节点的算法，包括二维数组，以自底向上的方式进行遍历。在二维数组的上下文中，BFS从给定的起始单元格开始遍历，并在移动到它们的邻居单元格之前探索其邻居单元格，以逐层方式进行。BFS在二维数组上的逐步解释如下：

初始化一个队列数据结构和一个辅助数据结构（例如访问数组），以跟踪访问过的单元格。
将起始单元格入队到队列中，并在辅助数据结构中标记为访问过。
开始一个循环，直到队列为空。
在循环中，从队列的前端出队一个单元格。该单元格表示正在访问的当前节点。
探索当前单元格的所有邻居单元格（上、下、左、右）。
对于每个未访问的邻居单元格，将其入队到队列中，并在辅助数据结构中标记为访问过。
重复步骤4到6，直到队列为空，表示已访问到与起始单元格相连的所有单元格。

Java执行

import java.util.LinkedList;
import java.util.Queue;
public class BFSTraversalOn2DArray {
   static class Cell {
      int row;
      int col;
   Cell(int row, int col) {
      this.row = row;
      this.col = col;
      }
   }
   public static void BFS_2D_Array(int[][] grid, int start_i, int start_j) {
      int rows = grid.length;
      int cols = grid[0].length;
      boolean[][] visited = new boolean[rows][cols];

   // Define the directions for exploring neighbors (up, down, left, right)
   int[] dr = {0, 0, 1, -1};
   int[] dc = {1, -1, 0, 0};

   Queue<Cell> queue = new LinkedList<>();

   queue.add(new Cell(start_i, start_j));
   visited[start_i][start_j] = true;

   while (!queue.isEmpty()) {
      Cell currentCell = queue.poll();
      int i = currentCell.row;
      int j = currentCell.col;
      System.out.println("Visiting cell at (" + i + ", " + j + ")"); // Print the visited cell

      for (int k = 0; k < 4; k++) { // Four directions: up, down, left, right
         int ni = i + dr[k];
         int nj = j + dc[k];

      // Check if the new cell (ni, nj) is within the grid boundaries
         if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && !visited[ni][nj]) { 
            queue.add(new Cell(ni, nj));
            visited[ni][nj] = true;
            }
         }
      }
   }
   public static void main(String[] args) {
      int[][] grid = {
         {1, 0, 1, 0},
         {0, 1, 0, 1},
         {1, 0, 1, 0}
   };
      int start_i = 1;
      int start_j = 2;

      System.out.println("Starting BFS traversal from cell (1, 2) in the 2D array.");
      BFS_2D_Array(grid, start_i, start_j);
   }
}

输出

Starting BFS traversal from cell (1, 2) in the 2D array.
Visiting cell at (1, 2)
Visiting cell at (1, 3)
Visiting cell at (1, 1)
Visiting cell at (2, 2)
Visiting cell at (0, 2)
Visiting cell at (2, 3)
Visiting cell at (0, 3)
Visiting cell at (1, 0)
Visiting cell at (2, 1)
Visiting cell at (0, 1)
Visiting cell at (2, 0)
Visiting cell at (0, 0)

矩阵的树形表示

Java 广度优先遍历 (BFS) 在使用JAVA的二维数组上

遍历二维数组

不同的遍历技巧：行主序和列主序

在使用BFS遍历2D数组时，可以选择行主序或列主序遍历。行主序是在迭代列之前迭代行，而列主序是在迭代行之前迭代列，这会根据内存布局影响BFS的性能。

处理边界情况

在对二维数组进行BFS时，正确处理边界情况非常重要。对数组边缘的单元格进行处理是至关重要的，因为它们缺少四个相邻单元格，需要避免错误。处理出界的单元格作为障碍物或忽略它们是必要的。

避免重复访问单元格和图中的循环

防止再次访问已处理的单元格以及处理二维数组图形的循环是必不可少的。使用哈希集等数据结构来标记已访问的单元格，在BFS期间跳过已访问的相邻单元格。

寻找最短路径

将BFS调整为在二维数组中寻找最短路径

将BFS调整为在二维数组中寻找最短路径。从源单元格开始，结束于目标单元格，BFS保持路径重构的父节点信息。

用于路径重构的父节点跟踪

在BFS过程中，对每个单元格跟踪父节点可以从目标回溯到源头重构最短路径。

处理障碍物和加权边在最短路径的上下文中

当二维数组中存在障碍物或加权边时，BFS应将障碍物标记为已访问，并根据加权边修改队列，以优先选择较低的权重进行更高效的最短路径计算。

在二维数组中，比较BFS和DFS

遍历图和二维数组的两种最基本的技术是广度优先遍历（BFS）和深度优先遍历（DFS）。BFS通过首先访问同一层上的节点来创建逐层探索。相反，深度优先搜索（DFS）在沿着每个分支尽可能远的情况下再逆向。

使用BFS还是DFS解决问题取决于问题的具体细节。当寻找最短路径或最少步数至关重要时，应使用BFS，因为它确保找到的第一个解决方案是最佳的。然而，当内存使用受限或对于给定路径存在许多解决方案时，建议使用DFS，因为在这些情况下它可能搜索更少的节点。选择BFS和DFS进行二维数组遍历的决定最终取决于问题的本质和期望的解决方案的特性。

BFS算法的现实应用

在机器人导航中使用二维地图上的BFS –
- 利用BFS指导机器人穿越表示为二维地图的复杂环境。
- 该算法逐层探索相邻的单元格，高效地找到最短路径。
- 使机器人能够避开障碍物，优化移动，并有效地到达目的地。
- 在自动驾驶汽车、仓储物流和机器人探索任务中被广泛应用。
基于BFS的路径规划算法 –
- 将BFS作为各种应用中的基本构建块用于路径规划。
- 用于视频游戏中为角色或NPC找到最佳路线。
- 在GPS和地图服务的路径规划中计算位置之间的最短路径。
- 应用于网络路由协议，以确保数据包的高效传输。