vlambda博客
学习文章列表

栈和深度优先搜索(DFS)

与 BFS 类似，深度优先搜索 （DFS）是用于在树/图中遍历/搜索的另一种重要算法。也可以在更抽象的场景中使用。

正如树的遍历中所提到的，我们可以用 DFS 进行 前序遍历，中序遍历 和 后序遍历。在这三个遍历顺序中有一个共同的特性：除非我们到达最深的结点，否则我们永远不会回溯。

这也是 DFS 和 BFS 之间最大的区别， BFS永远不会深入探索，除非它已经在当前层级访问了所有结点。

模版

递归模版

有两种实现 DFS 的方法。第一种方法是进行递归:

 
   
   
 
    
  
    
    
  
  1. boolean DFS(Node cur, Node target, Set<Node> visited) {
    2. 
  
    
    
  
  2.  return true if cur is target;
    3. 
  
    
    
  
  3.  for (next : each neighbor of cur) {
    4. 
  
    
    
  
  4.  if (next is not in visited) {
    5. 
  
    
    
  
  5.  add next to visted;
    6. 
  
    
    
  
  6.  return true if DFS(next, target, visited) == true;
    7. 
  
    
    
  
  7.  }
    8. 
  
    
    
  
  8.  }
    9. 
  
    
    
  
  9.  return false;
    10. 
  
    
    
  
  10. }
    11.

当我们递归地实现 DFS 时，似乎不需要使用任何栈。但实际上，我们使用的是由系统提供的隐式栈，也称为调用栈（Call Stack）。

显式栈模板

递归解决方案的优点是它更容易实现。但是，存在一个很大的缺点：如果递归的深度太高，你将遭受堆栈溢出。在这种情况下，您可能会希望使用 BFS，或使用 显式栈 实现 DFS。

 
   
   
 
    
  
    
    
  
  1. boolean DFS(int root, int target) {
    2. 
  
    
    
  
  2.  Set<Node> visited;
    3. 
  
    
    
  
  3.  Stack<Node> s;
    4. 
  
    
    
  
  4.  add root to s;
    5. 
  
    
    
  
  5.  while (s is not empty) {
    6. 
  
    
    
  
  6.  Node cur = the top element in s;
    7. 
  
    
    
  
  7.  return true if cur is target;
    8. 
  
    
    
  
  8.  for (Node next : the neighbors of cur) {
    9. 
  
    
    
  
  9.  if (next is not in visited) {
    10. 
  
    
    
  
  10.  add next to s;
    11. 
  
    
    
  
  11.  add next to visited;
    12. 
  
    
    
  
  12.  }
    13. 
  
    
    
  
  13.  }
    14. 
  
    
    
  
  14.  remove cur from s;
    15. 
  
    
    
  
  15.  }
    16. 
  
    
    
  
  16.  return false;
    17. 
  
    
    
  
  17. }
    18.

例题

1.岛屿数量

  • 难度： Medium

题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入: 11110
11010
11000
00000
输出: 1

示例 2:

输入: 11000
11000
00100
00011
输出: 3

解题思路及实现

笔者曾经在 这篇文章 中展示了如何使用 BFS 解决这道题，事实上该题使用 DFS 更简单，因为前者还需要一个队列维护 广度优先搜索 过程中搜索的层级信息。

使用 DFS 解题如下：

 
   
   
 
    
  
    
    
  
  1. public class B200NumIslands {
    2. 
  
    
    
  

    3. 
  
    
    
  
  3.  public int numIslands(char[][] grid) {
    4. 
  
    
    
  
  4.  int nr = grid.length;
    5. 
  
    
    
  
  5.  if (nr == 0) return 0;
    6. 
  
    
    
  
  6.  int nc = grid[0].length;
    7. 
  
    
    
  
  7.  if (nc == 0) return 0;
    8. 
  
    
    
  

    9. 
  
    
    
  
  9.  int result = 0;
    10. 
  
    
    
  

    11. 
  
    
    
  
  11.  for (int r = 0; r < nr; r++) {
    12. 
  
    
    
  
  12.  for (int c = 0; c < nc; c++) {
    13. 
  
    
    
  
  13.  if (grid[r][c] == '1') {
    14. 
  
    
    
  
  14.  result++;
    15. 
  
    
    
  
  15.  dfs(grid, r, c);
    16. 
  
    
    
  
  16.  }
    17. 
  
    
    
  
  17.  }
    18. 
  
    
    
  
  18.  }
    19. 
  
    
    
  

    20. 
  
    
    
  
  20.  return result;
    21. 
  
    
    
  
  21.  }
    22. 
  
    
    
  

    23. 
  
    
    
  
  23.  private void dfs(char[][] grid, int r, int c) {
    24. 
  
    
    
  
  24.  int nr = grid.length;
    25. 
  
    
    
  
  25.  int nc = grid[0].length;
    26. 
  
    
    
  

    27. 
  
    
    
  
  27.  // 排除边界外的情况
    28. 
  
    
    
  
  28.  if (r >= nr || c >= nc || r < 0 || c < 0) return;
    29. 
  
    
    
  
  29.  // 排除边界外指定位置为 '0' 的情况
    30. 
  
    
    
  
  30.  if (grid[r][c] == '0') return;
    31. 
  
    
    
  

    32. 
  
    
    
  
  32.  // 该位置为一个岛，标记为已探索
    33. 
  
    
    
  
  33.  grid[r][c] = '0';
    34. 
  
    
    
  

    35. 
  
    
    
  
  35.  dfs(grid, r - 1, c); // top
    36. 
  
    
    
  
  36.  dfs(grid, r + 1, c); // bottom
    37. 
  
    
    
  
  37.  dfs(grid, r, c - 1); // left
    38. 
  
    
    
  
  38.  dfs(grid, r, c + 1); // right
    39. 
  
    
    
  
  39.  }
    40. 
  
    
    
  
  40. }
    41.

2.克隆图

  • 难度： Medium

题目描述

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（ list[Node]）。

 
   
   
 
    
  
    
    
  
  1. class Node {
    2. 
  
    
    
  
  2.  public int val;
    3. 
  
    
    
  
  3.  public List<Node> neighbors;
    4. 
  
    
    
  
  4. }
    5.

更详细的题目描述参考 这里 : https://leetcode-cn.com/problems/clone-graph/

解题思路及实现

题目比较难理解，需要注意的是：

  1. 因为是 深拷贝 ，因此所有节点都需要通过 new 进行实例化，即需要遍历图中的每个节点，因此解决方案就浮现而出了，使用 DFS 或者 BFS 即可；

  2. 对每个已经复制过的节点进行标记，避免无限循环导致堆栈的溢出。

用 DFS 实现代码如下：

 
   
   
 
    
  
    
    
  
  1. class Solution {
    2. 
  
    
    
  
  2.  public Node cloneGraph(Node node) {
    3. 
  
    
    
  
  3.  HashMap<Node,Node> map = new HashMap<>();
    4. 
  
    
    
  
  4.  return dfs(node, map);
    5. 
  
    
    
  
  5.  }
    6. 
  
    
    
  

    7. 
  
    
    
  
  7.  private Node dfs(Node root, HashMap<Node,Node> map) {
    8. 
  
    
    
  
  8.  if (root == null) return null;
    9. 
  
    
    
  
  9.  if (map.containsKey(root)) return map.get(root);
    10. 
  
    
    
  

    11. 
  
    
    
  
  11.  Node clone = new Node(root.val, new ArrayList());
    12. 
  
    
    
  
  12.  map.put(root, clone);
    13. 
  
    
    
  
  13.  for (Node nei: root.neighbors) {
    14. 
  
    
    
  
  14.  clone.neighbors.add(dfs(nei, map));
    15. 
  
    
    
  
  15.  }
    16. 
  
    
    
  
  16.  return clone;
    17. 
  
    
    
  
  17.  }
    18. 
  
    
    
  
  18. }
    19.

3.目标和

  • 难度： Medium

题目描述

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 - 中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

 
   
   
 
    
  
    
    
  
  1. 输入: nums: [1, 1, 1, 1, 1], S: 3
    2. 
  
    
    
  
  2. 输出: 5
    3. 
  
    
    
  
  3. 解释:
    4. 
  
    
    
  

    5. 
  
    
    
  
  5. >-1+1+1+1+1 = 3
    6. 
  
    
    
  
  6. +1-1+1+1+1 = 3
    7. 
  
    
    
  
  7. +1+1-1+1+1 = 3
    8. 
  
    
    
  
  8. +1+1+1-1+1 = 3
    9. 
  
    
    
  
  9. +1+1+1+1-1 = 3
    10. 
  
    
    
  

    11. 
  
    
    
  
  11. 一共有5种方法让最终目标和为3。
    12.

注意:

1.数组非空，且长度不会超过20。2.初始的数组的和不会超过1000。3.保证返回的最终结果能被32位整数存下。

解题思路及实现

说实话这道题真没想到使用 DFS 暴力解决，还是经验太少了，这道题暴力解法是完全可以的，而且不会超时，因为题目中说了数组长度不会超过20，20个数字的序列，组合方式撑死了也就 2^20 种组合:

 
   
   
 
    
  
    
    
  
  1. public class Solution {
    2. 
  
    
    
  

    3. 
  
    
    
  
  3.  int count = 0;
    4. 
  
    
    
  

    5. 
  
    
    
  
  5.  public int findTargetSumWays(int[] nums, int S) {
    6. 
  
    
    
  
  6.  dfs(nums, 0, 0, S);
    7. 
  
    
    
  
  7.  return count;
    8. 
  
    
    
  
  8.  }
    9. 
  
    
    
  

    10. 
  
    
    
  
  10.  private void dfs(int[] nums, int index, int sum, int S) {
    11. 
  
    
    
  
  11.  if (index == nums.length) {
    12. 
  
    
    
  
  12.  if (sum == S) count++;
    13. 
  
    
    
  
  13.  } else {
    14. 
  
    
    
  
  14.  dfs(nums, index + 1, sum + nums[index], S);
    15. 
  
    
    
  
  15.  dfs(nums, index + 1, sum - nums[index], S);
    16. 
  
    
    
  
  16.  }
    17. 
  
    
    
  
  17.  }
    18. 
  
    
    
  
  18. }
    19.

4.二叉树的中序遍历

  • 难度： Medium

题目描述

给定一个二叉树，返回它的中序遍历。

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题思路及实现

二叉树相关真的是非常有趣的一个算法知识点（因为这道题非常具有代表性，我觉得面试考到的概率最高2333......），后续笔者会针对该知识点进行更详细的探究，本文列出两个解决方案。

1.递归法

 
   
   
 
    
  
    
    
  
  1. public class Solution {
    2. 
  
    
    
  

    3. 
  
    
    
  
  3.  // 1.递归法
    4. 
  
    
    
  
  4.  public List<Integer> inorderTraversal(TreeNode root) {
    5. 
  
    
    
  
  5.  List<Integer> list = new ArrayList<>();
    6. 
  
    
    
  
  6.  dfs(root, list);
    7. 
  
    
    
  
  7.  return list;
    8. 
  
    
    
  
  8.  }
    9. 
  
    
    
  

    10. 
  
    
    
  
  10.  private void dfs(TreeNode node, List<Integer> list) {
    11. 
  
    
    
  
  11.  if (node == null) return;
    12. 
  
    
    
  

    13. 
  
    
    
  
  13.  // 中序遍历：左中右
    14. 
  
    
    
  
  14.  if (node.left != null)
    15. 
  
    
    
  
  15.  dfs(node.left, list);
    16. 
  
    
    
  

    17. 
  
    
    
  
  17.  list.add(node.val);
    18. 
  
    
    
  

    19. 
  
    
    
  
  19.  if (node.right != null)
    20. 
  
    
    
  
  20.  dfs(node.right, list);
    21. 
  
    
    
  
  21.  }
    22. 
  
    
    
  
  22. }
    23.

2.使用栈

 
   
   
 
    
  
    
    
  
  1. public class Solution {
    2. 
  
    
    
  

    3. 
  
    
    
  
  3.  // 2.使用栈
    4. 
  
    
    
  
  4.  public List<Integer> inorderTraversal(TreeNode root) {
    5. 
  
    
    
  
  5.  List<Integer> list = new ArrayList<>();
    6. 
  
    
    
  
  6.  Stack<TreeNode> stack = new Stack<>();
    7. 
  
    
    
  

    8. 
  
    
    
  
  8.  TreeNode curr = root;
    9. 
  
    
    
  
  9.  while (!stack.isEmpty() || curr != null) {
    10. 
  
    
    
  
  10.  while (curr != null) {
    11. 
  
    
    
  
  11.  stack.push(curr);
    12. 
  
    
    
  
  12.  curr = curr.left;
    13. 
  
    
    
  
  13.  }
    14. 
  
    
    
  
  14.  curr = stack.pop();
    15. 
  
    
    
  
  15.  list.add(curr.val);
    16. 
  
    
    
  
  16.  curr = curr.right;
    17. 
  
    
    
  
  17.  }
    18. 
  
    
    
  
  18.  return list;
    19. 
  
    
    
  
  19.  }
    20. 
  
    
    
  
  20. }
    21.

参考 & 感谢

文章绝大部分内容节选自 LeetCode，栈和深度优先搜索 概述：

  • https://leetcode-cn.com/explore/learn/card/queue-stack/219/stack-and-dfs/

例题：

  • https://leetcode-cn.com/problems/number-of-islands

  • https://leetcode-cn.com/problems/clone-graph/

  • https://leetcode-cn.com/problems/target-sum/

  • https://leetcode-cn.com/problems/binary-tree-inorder-traversal/


推荐阅读

剑星 星刃 全支线任务汇总攻略-紧急信息 剑星 星刃 全支线任务汇总攻略-紧急信息
走迷宫之深度优先搜索（二） 走迷宫之深度优先搜索（二）

相关文章