使用 JAVA 在二维数组上进行广度优先遍历 (BFS)。

---

简介

广度优先遍历 (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)

矩阵的树形表示

遍历二维数组

• 不同的遍历技术：行优先与列优先

使用 BFS 遍历二维数组时，可以选择行优先或列优先遍历。行优先涉及在列之前迭代行，而列优先在行之前遍历列，这会根据内存布局影响 BFS 的性能。

• 处理边缘情况和边界条件

在二维数组上进行 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 和地图服务的路线规划中，计算位置之间的最短路径。

• 应用于网络路由协议以确保有效的数据包。

结论

二维数组上的广度优先遍历 (BFS) 是一种用于解决基于图的问题和迷宫的基本算法。Java 对 BFS 的实现使用队列数据结构有效地检查网格，为查找连接的组件、最短路径和解决各种难题提供了一种简洁而直接的方法。由于其适应性和 Java 的强大语言特性，BFS 是导航和分析二维数组的强大工具，有助于许多现实世界应用的成功。