資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 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 是導航和分析二維陣列的強大工具，有助於許多現實世界應用的成功。
2K+ 次檢視
