当前位置：首页 > news >正文

探讨Java深搜算法的学习笔记

news 2025/6/29 22:55:32

大家好，我是 V 哥。深度优先搜索（DFS）是一种图遍历算法，它优先深入到某条路径的尽头，再回溯到前一个节点继续探索其他路径，直到找到目标或遍历完整个图。DFS的应用场景广泛，可以用于路径搜索、连通性判断、迷宫求解等。以下是一个典型的DFS实现示例以及分析它在不同业务场景中的应用。

V 哥推荐：2024 最适合入门的 JAVA 课程

1. 先来看一个案例

以下为一个Java实现的DFS算法示例，用于在一个二维矩阵中寻找从起点到终点的路径。该矩阵中1表示可以通过的点，0表示障碍物。目标是找到从起点（0,0）到终点（m-1,n-1）的路径。

public class DFSMazeSolver {private static final int[] DX = {-1, 1, 0, 0}; // 行移动方向：上，下private static final int[] DY = {0, 0, -1, 1}; // 列移动方向：左，右public boolean dfs(int[][] maze, int x, int y, boolean[][] visited) {int rows = maze.length;int cols = maze[0].length;// 边界条件与目标判断if (x < 0 || y < 0 || x >= rows || y >= cols || maze[x][y] == 0 || visited[x][y]) {return false;}// 到达终点if (x == rows - 1 && y == cols - 1) {return true;}// 标记当前位置已访问visited[x][y] = true;// 递归地探索四个方向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("路径可达");} else {System.out.println("无可行路径");}}
}

代码说明

DFS主逻辑：dfs方法用于在当前位置（x，y）开始深度优先搜索。
边界条件：包括是否越界、是否遇到障碍物以及是否已经访问。
终点判断：当到达矩阵右下角终点（rows-1，cols-1）时，返回true。
回溯处理：在搜索过程中，为了避免重复访问，将访问过的位置标记为已访问，若搜索失败则回溯重置。

2. 业务场景分析

迷宫或地图导航：DFS可用于迷宫或地图路径导航，寻找从起点到终点的路径。在实际应用中，可以在机器人路径规划、无人机飞行路径规划中使用类似的DFS算法。
权限和连通性检测：在网络安全中，DFS可以用于检测用户权限或系统连通性，例如检测某用户在权限网络中的访问路径，确保系统关键资源安全。
社交网络分析：在社交网络中，DFS可以用于分析用户关系连通性，例如寻找两个人之间的关系链路、推荐相似好友。
数据爬取：DFS算法也可用于数据爬取，从起始页面开始深度爬取相关页面信息。

在机器人路径规划和无人机飞行路径规划中，DFS算法可以用来寻找从起点到目标点的可行路径。DFS适合在地图较小且需要找到任意一条可行路径的场景。以下是一个在网格地图上实现DFS的完整Java代码示例，模拟机器人或无人机在二维平面上寻找从起点到目标点的路径。

如何实现无人机飞行路径规划

假设网格中的0表示障碍物，1表示可通行区域。目标是从起点（0, 0）到终点（m-1, n-1）找到一条通路。

import java.util.ArrayList;
import java.util.List;public class RobotPathPlanner {// 定义四个方向：上，下，左，右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"};// 存储路径private List<String> path = new ArrayList<>();// 深度优先搜索算法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;}// 如果到达终点位置，路径规划成功if (x == rows - 1 && y == cols - 1) {path.add("(" + x + "," + y + ")");return true;}// 标记当前节点为已访问visited[x][y] = true;path.add("(" + x + "," + y + ")");// 遍历四个方向进行递归搜索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;}}// 回溯：撤销当前路径点的访问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("规划路径：");for (String step : path) {System.out.println(step);}}
}