【第二十二天 - DFS 介绍】

Q1. DFS 是什麽

• Depth-First Search (DFS) 是一种走访 Graph 的策略，以深度优先，只要遇到能走的路，就先继续往下走，直到无路可走才返回上一层走其他条路。

• 以下图为例，以最上方的节点为起点，以数字代表走访顺序。

  • 在走访节点 0 时，发现有三条路可以往下走。
    

  • 先走一条路，到达节点 1 ，此时又发现了两条路。
    

  • 由於以深度优先，因此先不走节点 0 的另外两条路，而是从节点 1 继续往下走。此时走到节点 2 後，又发现一条路。

  

  • 走访节点 3，接下来已无路可走，於是返回节点 2，亦无路可走，於是再返回节点 1 。

  

  • 走节点 1 的另外一条路到节点 4，发现一条路。
    

  • 节点 4 有一条路可走，但走过去发现是已经走访过的节点 0，因此其实无路可走了。原路返回至节点 1 ，再返回至节点 0 ，走最後一条路到节点 5 。

  

  • 节点 5 无路可走，返回节点 0 。节点 0 作为起点，也已经无路可走了，此时便完成了起点为节点 0 的 DFS 走访。

  

• 时常与 DFS 一起讨论的还有 BFS

Q2. 学会 DFS 概念可以做什麽 ?

• 机器人走迷宫、数独
• 检查 Graph 是否有回圈
• 找寻 Graph 中连接两点的路径

Lab. 明天要解的题目：112. Path Sum

• 题目连结：https://leetcode.com/problems/path-sum/

• 题目叙述：

  • 会给一个二元树与目标总和
  • 要找一个从 root 到 leaf 的路径，加总为目标总和
    

• 测资的 Input/Output

  • 若找到 root 到 leaf 的路径相加的总和为目标值，则回传 true，反之，回传 false
    

  

• 题目限制

  • 二元数总共有 0~5000 个 Node
  • 每个 Node 的值介於 -1000~1000
  • 目标值为 -1000~1000