iT邦幫忙

2021 iThome 鐵人賽

DAY 22
0
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 22

【第二十二天 - DFS 介紹】

Q1. DFS 是什麼

  • Depth-First Search (DFS) 是一種走訪 Graph 的策略,以深度優先,只要遇到能走的路,就先繼續往下走,直到無路可走才返回上一層走其他條路。

  • 以下圖為例,以最上方的節點為起點,以數字代表走訪順序。

    • 在走訪節點 0 時,發現有三條路可以往下走。
      https://ithelp.ithome.com.tw/upload/images/20210922/20140592AubYq4ou6N.png

    • 先走一條路,到達節點 1 ,此時又發現了兩條路。
      https://ithelp.ithome.com.tw/upload/images/20210922/20140592V4CAcnrqqL.png

    • 由於以深度優先,因此先不走節點 0 的另外兩條路,而是從節點 1 繼續往下走。此時走到節點 2 後,又發現一條路。

    https://ithelp.ithome.com.tw/upload/images/20210922/20140592x2FuUK3klc.png

    • 走訪節點 3,接下來已無路可走,於是返回節點 2,亦無路可走,於是再返回節點 1 。

    https://ithelp.ithome.com.tw/upload/images/20210922/20140592Ktjea2tSUU.png

    • 走節點 1 的另外一條路到節點 4,發現一條路。
      https://ithelp.ithome.com.tw/upload/images/20210922/201405926ecp26ohrl.png

    • 節點 4 有一條路可走,但走過去發現是已經走訪過的節點 0,因此其實無路可走了。原路返回至節點 1 ,再返回至節點 0 ,走最後一條路到節點 5 。

    https://ithelp.ithome.com.tw/upload/images/20210922/20140592HmubsKCdga.png

    • 節點 5 無路可走,返回節點 0 。節點 0 作為起點,也已經無路可走了,此時便完成了起點為節點 0 的 DFS 走訪。

    https://ithelp.ithome.com.tw/upload/images/20210922/20140592SQHVWbRoZV.png

  • 時常與 DFS 一起討論的還有 BFS

Q2. 學會 DFS 概念可以做什麼 ?

  • 機器人走迷宮、數獨
  • 檢查 Graph 是否有迴圈
  • 找尋 Graph 中連接兩點的路徑

Lab. 明天要解的題目:112. Path Sum

  • 題目連結:https://leetcode.com/problems/path-sum/

  • 題目敘述:

    • 會給一個二元樹與目標總和
    • 要找一個從 root 到 leaf 的路徑,加總為目標總和
      https://ithelp.ithome.com.tw/upload/images/20210922/20140592FEnBY8Xakf.png
  • 測資的 Input/Output

    • 若找到 root 到 leaf 的路徑相加的總和為目標值,則回傳 true,反之,回傳 false
      https://ithelp.ithome.com.tw/upload/images/20210922/20140592nB14GpgGlf.png

    https://ithelp.ithome.com.tw/upload/images/20210922/20140592OZkDbiuktW.png

  • 題目限制

    • 二元數總共有 0~5000 個 Node
    • 每個 Node 的值介於 -1000~1000
    • 目標值為 -1000~1000
      https://ithelp.ithome.com.tw/upload/images/20210922/20140592kt3zUEfbNw.png

上一篇
【第二十一天 - Graph 題目分析】
下一篇
【第二十三天 - DFS 題目分析】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言