Day9 -- Brute Force - DFS & BFS - iT 邦幫忙

今天會是最後一天介紹Brute Force類別的演算法，而今天要講的內容是 Depth-First Search(DFS) 和 Breadth-First Search(BFS) ，這兩種演算法基本上都是拿來計算點對點 ... 第12屆iThome鐵人賽 DAY 9 0 SoftwareDevelopment 舌尖上的演算法系列第 9篇 Day9--BruteForce-DFS&BFS 12th鐵人賽 algorithm 資料結構與演算法 informistry-hanklee adslbbcc1949 團隊海狗部隊 2020-09-1613:20:123571瀏覽 本系列文章同步分享於個人Blog→InformisTry-HankLee 前言 應該有人跟我一樣真心覺得BruteForce其實看起來也沒什麼，就都是很簡單的邏輯和實作方式，希望到目前為止大家都能理解。

今天會是最後一天介紹BruteForce類別的演算法，而今天要講的內容是Depth-FirstSearch(DFS)和Breadth-FirstSearch(BFS)，這兩種演算法基本上都是拿來計算點對點之間的關聯，而具體這兩種方式是怎麼運作的呢？讓我們接著看下去。

遇到的問題？ 上面提到DFS和BFS是用來計算點對點之間的關聯，用簡化的圖來表示的話，大概可以用上方的圖來舉例，會把資料設定成節點與連線，但是實際上需要用到這兩種方式解決的問題是什麼呢？最簡單最貼近生活的例子就是路徑導航，路徑導航其實也就是用點對點串起來計算最短的路徑，另外，當然也是可以拿到解謎宮的路線，或著計算電力網的串連是否完善等。

例子很多，但我感覺路徑導航是最容易想像的問題。

Depth-FirstSearch(DFS) Depth-FirstSearch在進行的過程中，會跑過所有的節點(Node)，並在跑過的節點做上記號，並記錄順序，直到所有的節點都有了記號，流程如下： 先決定一個起始節點，並將其做上記號。

從這個節點開始，去尋找下一個相連但無記號的節點，並將這個新的節點做上記號。

反覆第二個步驟，直到進行到了一個不再與其他節點相連的節點（deadend)。

從deadend的節點進行『返回追蹤』，找出『上一個』還有相連節點沒被做上記號的節點，然後在進行第二個步驟。

反覆上述步驟，直到所有節點都做上了記號。

讓我們看看下面動圖來讓我們更了解這個流程： 有幾點特別提出來解釋一下： 當流程跑到節點Ｃ的時候，一開始原本是連線到節點Ａ，但是後來發現節點Ａ已經做過記號，表示在Output中已經有節點Ａ的紀錄了，因此才轉換成下一個節點Ｄ。

（綠色虛線表示該連線對象已有紀錄） 當流程跑到節點Ｆ之後，因為節點Ｆ已經是不再有相連且無記號的節點，因此之後開始進行返回追蹤，直到找到節點Ｃ還有其他節點沒有記號，因此再從節點Ｃ去連下一個節點。

Breadth-FirstSearch(BFS) Breadth-FirstSearch跟Depth-FirstSearch一樣，也是會跑過所有的節點，一樣嘢是在跑過的節點上做記號，然後記錄順序，但是不同的地方是BFS是『分層』的概念去進行整個流程，整體流程如下： 先決定一個起始節點，並將其做上記號。

針對這個起始節點，依次紀錄所有的鄰居節點，並在這些節點上做記號。

當對於起始節點的所有鄰居節點都記錄過後，再從第一個鄰居節點開始重複第二步驟。

依序上述步驟反覆進行，直到所有節點都有記號。

再讓我們看看BFS的動圖來熟悉一下流程： Depth-FirstSearch和Breadth-FirstSearch兩者都可以用來求出節點間的關聯性，而Breadth-FirstSearch還可以用來尋找最短路徑。

DFS和BFS的時間複雜度 還記得第四天我們講抽象資料型別介紹Graph（忘記的可以點這裡複習)時，有提到Graph可以轉換成AdjacencyMatrix和AdjacencyList，而DFS和BFS在進行時針對的抽象資料型別就是Graph，所以這兩個演算法的時間複雜度也會因為所使用的資料結構（AdjacencyMatrix和AdjacencyList）而有所不同： Efficiency DFS BFS AdjacencyMatrix O(｜V^2｜) O(｜V^2｜) AdjacencyList O(｜V｜+｜E｜) O(｜V｜+｜E｜) Ｖ：節點(Node)數；Ｅ：連線(Edge)數 小結 ＤＦＳ和ＢＦＳ用來解決與Graph相關的問題。

ＤＦＳ是一個節點一個節點進行，而ＢＦＳ是一層節點一層節點進行。

ＤＦＳ和ＢＦＳ的時間複雜度會依據所使用的資料結構AdjacencyMatrix和AdjacencyList而有所不同。

預告 明天我們將會介紹新的演算法類別-DecreaseandConquer及其一個演算法-InsertionSort。

References IntroductiontotheDesignandAnalysisofAlgorithms,3rdEdition,byAnanyLevitin 留言 追蹤 檢舉 上一篇 Day8--BruteForce-Knapsack 下一篇 Day10--DecreaseandConquer-InsertionSort 系列文 舌尖上的演算法 共30篇 目錄 RSS系列文 訂閱系列文 25人訂閱 26 Day26--GreedyTechniques-Kruskal'sAlgorithm 27 Day27--GreedyTechniques-Dijkstra'sAlgorithm 28 Day28--Sudoku-Backtracking 29 Day29--Sudoku-AlgorithmX 30 Day30--AlgorithmXandSudoku 完整目錄 尚未有邦友留言 立即登入留言 iT邦幫忙鐵人賽 參賽組數 1087組 團體組數 52組 累計文章數 20485篇 完賽人數 572人 鐵人賽最新文章 資料驗證(golang)(Day23) .NetCoreWebApi_筆記22_Swagger自訂文件並讀取API註解描述 [Day??]2021iThome鐵人賽-頒獎典禮@2022.01.08‧輔仁大學 [Day33]HexoxNexT-顯示最新文章、導入GoogleAnalytics的坑 【Day31】新加坡工作後續的時程 重構原本的內容(golang)(Day22) Laravel-jQueryAJAX範例 2022/1/2更新 .NetCoreWebApi_筆記21_Swagger及OpenAPI介紹與配置使用方式_API管理與測試探討 .NetCoreWebApi_筆記20_api結合ADO.NET資料庫操作part8_新聞文章查詢 前往鐵人賽 技術推廣專區 [Day2]抓取每日收盤價 [Day1]基本工具安裝 利用python取得永豐銀行API的Nonce [Day03]tinyML開發板介紹 永豐金融API測試員 [Day01]在享受tinyML這道美食之前 [Day3]使用ta-lib製作指標 [Day4]函數打包與買進持有報酬率試算 計算API所需要的參數:HashID 計算API所需要的參數:IV 前往鐵人賽 熱門問題 中華電信企業資安攻擊名稱HTTP-APACHE-LOG4j2-BODY6-RCE 40人小公司用的郵件伺服器 急救！將ImageView傳到另一個頁面 關於團隊合作 正航ERP相關問題 資安宣導文案 請問有哪位好心人能借一下百度帳號... 請教SQL大師，如何在GROUPBY分群裡找出組別最多筆數量的組別名稱 [已解決]急!!!csv匯入MySQLWorkbench出現錯誤訊息請問如何解決 C#如何將資料庫的每個字元從原本的(ascii編碼)逐一轉成(utf8編碼) IT邦幫忙 站方公告 【2021iThome鐵人賽】登登登！究竟獎落誰家，2021iThome鐵人賽得獎名單正式揭曉 熱門tag 看更多 13th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 2018鐵人賽 javascript 2017鐵人賽 windows php python windowsserver linux c# 程式設計 資訊安全 css vue.js sql 分享 熱門回答 40人小公司用的郵件伺服器 關於團隊合作 資安宣導文案 SVN版本控制的選擇 python檔案計算問題 [已解決]急!!!csv匯入MySQLWorkbench出現錯誤訊息請問如何解決 C#如何將資料庫的每個字元從原本的(ascii編碼)逐一轉成(utf8編碼) 正航ERP相關問題 為什麼Visualstudio查詢資料庫資料會顯示 中華電信企業資安攻擊名稱HTTP-APACHE-LOG4j2-BODY6-RCE 熱門文章 【Day31】新加坡工作後續的時程 2021法遵科技與電腦稽核專題競賽-賀雲科大、逢甲、北商大、中正、致理科大、亞洲科大等學校隊伍獲獎，培育智慧法遵與AI稽核人才邁向國際~ Laravel-jQueryAJAX範例 [Day33]HexoxNexT-顯示最新文章、導入GoogleAnalytics的坑 【徵才】台北中山區-知名航空貨運-資訊網管人員 重構原本的內容(golang)(Day22) 科學家與研究生的關係研究篇 [Day??]2021iThome鐵人賽-頒獎典禮@2022.01.08‧輔仁大學 30天Python自學:Day01 印表機維修五種常見故障，若遇到問題就能先自己排除了 一週點數排行 更多點數排行 海綿寶寶(antijava) Gary(mosbbs) raytracy(raytracy) 一級屠豬士(hitomitanaka) Samuel(kuanyu) ccenjor(ccenjor) 居然解出來了(partyyaya) horace_work(horace_work) 純真的人(jer5173) souda(souda) × At 輸入對方的帳號或暱稱 Loading 找不到結果。

標記 {{result.label}} {{result.account}} 關閉