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

算法学习笔记:6.深度优先搜索算法——从原理到实战,涵盖 LeetCode 与考研 408 例题

在计算机科学领域,搜索算法是解决问题的重要工具,其中深度优先搜索(Depth-First Search,简称 DFS)凭借其简洁高效的特性,在图论、回溯、拓扑排序等众多场景中发挥着关键作用。无论是 LeetCode 算法题,还是考研计算机专业基础综合(408)考试,深度优先搜索都是高频考点。

深度优先搜索算法核心思路

深度优先搜索的基本思想是沿着一条路径尽可能深地探索,直到无法继续或达到目标状态,然后回溯到上一个节点,继续探索其他路径,直至遍历完所有可达节点。在图结构或树结构中,DFS 可以用来遍历所有节点、寻找路径、检测连通性等。

1.1 算法实现方式

DFS 通常有两种实现方式:递归和迭代(借助栈数据结构)。

  • 递归实现:利用函数调用栈,从起始节点开始,不断递归访问相邻节点,当达到边界条件(如访问过的节点、无相邻节点)时回溯。代码简洁直观,但可能因递归深度过深导致栈溢出。
  • 迭代实现:手动维护一个栈,将起始节点入栈,每次取出栈顶节点,访问其未访问过的相邻节点并将其入栈,直到栈为空。这种方式可避免栈溢出问题,适用于大规模数据。

1.2 算法流程

以图结构为例,DFS 的基本流程如下:

  1. 选择一个起始节点,标记为已访问。
  1. 从起始节点出发,找到一个未访问的相邻节点,将其标记为已访问,并以该节点为新的起始节点,递归执行步骤 2。
  1. 当当前节点的所有相邻节点都已访问时,回溯到上一个节点,继续执行步骤 2。
  1. 重复步骤 2 和 3,直到所有可达节点都被访问。

绘制出的 DFS 递归实现的流程图:

为了更直观地理解,假设我们有如下无向图:

从节点 A 开始进行 DFS,访问顺序可能为 A -> B -> D -> E -> C(顺序不唯一,取决于具体实现)。

LeetCode 例题实战

例题 1:200. 岛屿数量

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。

示例 1:

输入:grid = [

["1","1","1","1","0"],

["1","1","0","1","0"],

["1","1","0","0","0"],

["0","0","0","0","0"]

]

输出:1

解题思路:使用 DFS 遍历二维网格,当遇到'1'时,将其及其相邻的'1'全部标记为已访问(可以将'1'改为'0'),每完成一次 DFS,岛屿数量加 1。


public class NumIslands {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int count = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {dfs(grid, i, j);count++;}}}return count;}private void dfs(char[][] grid, int i, int j) {int m = grid.length;int n = grid[0].length;if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {return;}grid[i][j] = '0';dfs(grid, i - 1, j);dfs(grid, i + 1, j);dfs(grid, i, j - 1);dfs(grid, i, j + 1);}}

例题 2:79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中 “相邻” 单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

输出:true

解题思路:从网格中的每个单元格开始进行 DFS,当当前字符与单词当前字符匹配时,继续向相邻单元格递归搜索。为避免重复访问,使用一个布尔数组记录单元格是否已被访问。如果找到匹配的路径,返回true;遍历完所有单元格仍未找到,则返回false。

public class WordSearch {public boolean exist(char[][] board, String word) {int m = board.length;int n = board[0].length;boolean[][] visited = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (dfs(board, word, 0, i, j, visited)) {return true;}}}return false;}private boolean dfs(char[][] board, String word, int index, int i, int j, boolean[][] visited) {int m = board.length;int n = board[0].length;if (index == word.length()) {return true;}if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(index)) {return false;}visited[i][j] = true;boolean result = dfs(board, word, index + 1, i - 1, j, visited) ||dfs(board, word, index + 1, i + 1, j, visited) ||dfs(board, word, index + 1, i, j - 1, visited) ||dfs(board, word, index + 1, i, j + 1, visited);visited[i][j] = false;return result;}}

考研 408 例题分析

例题:已知一个无向连通图的邻接表存储结构,编写算法判断图中是否存在回路。

解题思路:利用 DFS 遍历图,在遍历过程中记录每个节点的前驱节点。当访问到一个已访问过的节点,且该节点不是当前节点的前驱节点时,说明存在回路。

import java.util.ArrayList;import java.util.List;class Graph {int V;List<List<Integer>> adj;Graph(int v) {V = v;adj = new ArrayList<>(v);for (int i = 0; i < v; i++) {adj.add(new ArrayList<>());}}void addEdge(int v, int w) {adj.get(v).add(w);adj.get(w).add(v);}boolean isCyclic() {boolean[] visited = new boolean[V];for (int i = 0; i < V; i++) {if (!visited[i]) {if (dfs(i, -1, visited)) {return true;}}}return false;}private boolean dfs(int v, int parent, boolean[] visited) {visited[v] = true;for (int i : adj.get(v)) {if (!visited[i]) {if (dfs(i, v, visited)) {return true;}} else if (i != parent) {return true;}}return false;}}public class CyclicGraph {public static void main(String[] args) {Graph g1 = new Graph(5);g1.addEdge(1, 0);g1.addEdge(0, 2);g1.addEdge(2, 1);g1.addEdge(0, 3);g1.addEdge(3, 4);if (g1.isCyclic()) {System.out.println("Graph contains cycle");} else {System.out.println("Graph does not contain cycle");}Graph g2 = new Graph(3);g2.addEdge(0, 1);g2.addEdge(1, 2);if (g2.isCyclic()) {System.out.println("Graph contains cycle");} else {System.out.println("Graph does not contain cycle");}}}

总结

深度优先搜索算法以其独特的搜索策略,在解决各类问题中展现出强大的能力。通过 LeetCode 例题和考研 408 真题的实战演练,我们不仅掌握了 DFS 在不同场景下的应用,还熟悉了其 Java 代码实现。在实际编程和考研备考中,熟练运用 DFS 算法,能够有效提升问题解决能力。后续可以进一步研究 DFS 与其他算法的结合应用,探索其在更复杂场景下的优化与拓展。

希望本文能够帮助读者更深入地理解深度优先搜索算法,并在实际项目中发挥其优势。谢谢阅读!


希望这份博客能够帮助到你。如果有其他需要修改或添加的地方,请随时告诉我。

http://www.xdnf.cn/news/1080901.html

相关文章:

  • 风平浪静、无事发生
  • 八股学习(三)---MySQL
  • 【C语言刷题】第十天:加量加餐继续,代码题训练,融会贯通IO模式
  • 类图+案例+代码详解:软件设计模式----原型模式
  • WPF+HelixToolkit打造炫酷自定义3D贴图立方体盒子模型
  • goole chrome变更默认搜索引擎为百度
  • 篇二 OSI七层模型,TCP/IP四层模型,路由器与交换机原理
  • SpringBoot-规划多模块目录结构
  • 从0开始学习R语言--Day38--辛普森多样性指数
  • Nuxt 3 面试题合集(中高级)
  • vue3 获取选中的el-table行数据
  • 浅谈 webshell 构造之如何获取恶意函数
  • 「AI产业」| 《中国信通院华为:智能体技术和应用研究报告》
  • Response对象
  • Excel 如何处理更复杂的嵌套逻辑判断?
  • 网安系列【4】之OWASP与OWASP Top 10:Web安全入门指南
  • Flink Vitess CDC 环境配置与验证
  • QString 转 varchar
  • 【网络与系统安全】域类实施模型DTE
  • 数字资产革命中的信任之锚:RWA法律架构的隐形密码
  • ORACLE 日常查询
  • 浏览器(Chrome /Edge)高效使用 - 内部命令/快捷键/启动参数
  • vue3 el-table 行筛选 设置为单选
  • python打卡day57@浙大疏锦行
  • C#引用类型
  • 代码随想录算法训练营第四十六天|动态规划part13
  • WPF_Reactive_控件调试方法
  • PortSwigger Labs SQLInjection LAB6-7
  • Golang 运算符
  • 3D建模公司的能力与技术