大家好，我是 V 哥。深度優(yōu)先搜索（DFS）是一種圖遍歷算法，它優(yōu)先深入到某條路徑的盡頭，再回溯到前一個(gè)節(jié)點(diǎn)繼續(xù)探索其他路徑，直到找到目標(biāo)或遍歷完整個(gè)圖。DFS的應(yīng)用場(chǎng)景廣泛，可以用于路徑搜索、連通性判斷、迷宮求解等。以下是一個(gè)典型的DFS實(shí)現(xiàn)示例以及分析它在不同業(yè)務(wù)場(chǎng)景中的應(yīng)用。

V 哥推薦：2024 最適合入門的 JAVA 課程

1. 先來看一個(gè)案例

以下為一個(gè)Java實(shí)現(xiàn)的DFS算法示例，用于在一個(gè)二維矩陣中尋找從起點(diǎn)到終點(diǎn)的路徑。該矩陣中1表示可以通過的點(diǎn)，0表示障礙物。目標(biāo)是找到從起點(diǎn)（0,0）到終點(diǎn)（m-1,n-1）的路徑。

public class DFSMazeSolver {private static final int[] DX = {-1, 1, 0, 0}; // 行移動(dòng)方向：上，下private static final int[] DY = {0, 0, -1, 1}; // 列移動(dòng)方向：左，右public boolean dfs(int[][] maze, int x, int y, boolean[][] visited) {int rows = maze.length;int cols = maze[0].length;// 邊界條件與目標(biāo)判斷if (x < 0 || y < 0 || x >= rows || y >= cols || maze[x][y] == 0 || visited[x][y]) {return false;}// 到達(dá)終點(diǎn)if (x == rows - 1 && y == cols - 1) {return true;}// 標(biāo)記當(dāng)前位置已訪問visited[x][y] = true;// 遞歸地探索四個(gè)方向for (int i = 0; i < 4; i++) {int newX = x + DX[i];int newY = y + DY[i];if (dfs(maze, newX, newY, visited)) {return true;}}// 回溯visited[x][y] = false;return false;}public boolean canSolveMaze(int[][] maze) {int rows = maze.length;int cols = maze[0].length;boolean[][] visited = new boolean[rows][cols];return dfs(maze, 0, 0, visited);}public static void main(String[] args) {int[][] maze = {{1, 0, 0, 0},{1, 1, 0, 1},{0, 1, 0, 0},{1, 1, 1, 1}};DFSMazeSolver solver = new DFSMazeSolver();if (solver.canSolveMaze(maze)) {System.out.println("路徑可達(dá)");} else {System.out.println("無可行路徑");}}
}

代碼說明

1. DFS主邏輯：dfs方法用于在當(dāng)前位置（x，y）開始深度優(yōu)先搜索。
2. 邊界條件：包括是否越界、是否遇到障礙物以及是否已經(jīng)訪問。
3. 終點(diǎn)判斷：當(dāng)?shù)竭_(dá)矩陣右下角終點(diǎn)（rows-1，cols-1）時(shí)，返回true。
4. 回溯處理：在搜索過程中，為了避免重復(fù)訪問，將訪問過的位置標(biāo)記為已訪問，若搜索失敗則回溯重置。

2. 業(yè)務(wù)場(chǎng)景分析

1. 迷宮或地圖導(dǎo)航：DFS可用于迷宮或地圖路徑導(dǎo)航，尋找從起點(diǎn)到終點(diǎn)的路徑。在實(shí)際應(yīng)用中，可以在機(jī)器人路徑規(guī)劃、無人機(jī)飛行路徑規(guī)劃中使用類似的DFS算法。

2. 權(quán)限和連通性檢測(cè)：在網(wǎng)絡(luò)安全中，DFS可以用于檢測(cè)用戶權(quán)限或系統(tǒng)連通性，例如檢測(cè)某用戶在權(quán)限網(wǎng)絡(luò)中的訪問路徑，確保系統(tǒng)關(guān)鍵資源安全。

3. 社交網(wǎng)絡(luò)分析：在社交網(wǎng)絡(luò)中，DFS可以用于分析用戶關(guān)系連通性，例如尋找兩個(gè)人之間的關(guān)系鏈路、推薦相似好友。

4. 數(shù)據(jù)爬取：DFS算法也可用于數(shù)據(jù)爬取，從起始頁面開始深度爬取相關(guān)頁面信息。

在機(jī)器人路徑規(guī)劃和無人機(jī)飛行路徑規(guī)劃中，DFS算法可以用來尋找從起點(diǎn)到目標(biāo)點(diǎn)的可行路徑。DFS適合在地圖較小且需要找到任意一條可行路徑的場(chǎng)景。以下是一個(gè)在網(wǎng)格地圖上實(shí)現(xiàn)DFS的完整Java代碼示例，模擬機(jī)器人或無人機(jī)在二維平面上尋找從起點(diǎn)到目標(biāo)點(diǎn)的路徑。

如何實(shí)現(xiàn)無人機(jī)飛行路徑規(guī)劃

假設(shè)網(wǎng)格中的0表示障礙物，1表示可通行區(qū)域。目標(biāo)是從起點(diǎn)（0, 0）到終點(diǎn)（m-1, n-1）找到一條通路。

import java.util.ArrayList;
import java.util.List;public class RobotPathPlanner {// 定義四個(gè)方向：上，下，左，右private static final int[] DX = {-1, 1, 0, 0};private static final int[] DY = {0, 0, -1, 1};private static final String[] DIRECTION = {"Up", "Down", "Left", "Right"};// 存儲(chǔ)路徑private List<String> path = new ArrayList<>();// 深度優(yōu)先搜索算法public boolean dfs(int[][] grid, int x, int y, boolean[][] visited) {int rows = grid.length;int cols = grid[0].length;// 邊界條件：檢查是否越界，是否遇到障礙物，是否已訪問if (x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] == 0 || visited[x][y]) {return false;}// 如果到達(dá)終點(diǎn)位置，路徑規(guī)劃成功if (x == rows - 1 && y == cols - 1) {path.add("(" + x + "," + y + ")");return true;}// 標(biāo)記當(dāng)前節(jié)點(diǎn)為已訪問visited[x][y] = true;path.add("(" + x + "," + y + ")");// 遍歷四個(gè)方向進(jìn)行遞歸搜索for (int i = 0; i < 4; i++) {int newX = x + DX[i];int newY = y + DY[i];if (dfs(grid, newX, newY, visited)) {path.add(DIRECTION[i]);return true;}}// 回溯：撤銷當(dāng)前路徑點(diǎn)的訪問path.remove(path.size() - 1);visited[x][y] = false;return false;}public List<String> findPath(int[][] grid) {int rows = grid.length;int cols = grid[0].length;boolean[][] visited = new boolean[rows][cols];if (dfs(grid, 0, 0, visited)) {return path;} else {path.add("No Path Found");return path;}}public static void main(String[] args) {int[][] grid = {{1, 0, 0, 0},{1, 1, 0, 1},{0, 1, 1, 0},{1, 0, 1, 1}};RobotPathPlanner planner = new RobotPathPlanner();List<String> path = planner.findPath(grid);System.out.println("規(guī)劃路徑：");for (String step : path) {System.out.println(step);}}
}

來解釋一下代碼

1. 方向定義：DX和DY分別代表在網(wǎng)格上移動(dòng)的方向數(shù)組，DIRECTION數(shù)組用于記錄方向名稱，便于輸出路徑。
2. DFS遞歸搜索：dfs方法從指定位置(x, y)開始搜索，檢查越界、障礙物和訪問狀態(tài)。
3. 終點(diǎn)判斷：到達(dá)終點(diǎn)時(shí)返回true，并將路徑記錄到path列表。
4. 回溯：如果當(dāng)前路徑無效，則回溯并撤銷該路徑點(diǎn)的訪問狀態(tài)。
5. 路徑輸出：主函數(shù)findPath調(diào)用dfs，并根據(jù)DFS結(jié)果返回路徑或“未找到路徑”的提示。

機(jī)器人路徑規(guī)劃：在倉儲(chǔ)物流中，機(jī)器人需要規(guī)劃從起點(diǎn)到指定位置的路徑，避開障礙物（如貨架），通過DFS可以找到一條可行的路徑。

無人機(jī)飛行路徑規(guī)劃：在室內(nèi)或復(fù)雜地形中，無人機(jī)可以通過DFS找到安全飛行路線，避開障礙物，確保抵達(dá)目的地。DFS適用于場(chǎng)地相對(duì)較小且只需找到一條路徑的場(chǎng)景。

3. 最后的注意事項(xiàng)

1. 性能：在較大區(qū)域或復(fù)雜地形中，DFS可能導(dǎo)致大量回溯?？梢杂肁*或Dijkstra等啟發(fā)式算法優(yōu)化。
2. 障礙動(dòng)態(tài)性：如果障礙物可能移動(dòng)，可以定期重新規(guī)劃路徑。

關(guān)注威哥愛編程，編碼路上V哥陪你不寂寞。