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