【Day33】[演算法]-深度優先搜尋DFS與廣度優先搜尋BFS

深度優先搜尋DFS ... 先選定一個頂點開始走訪，接著從此頂點相鄰未被走過的頂點中，擇一走訪標示為記錄點，以此類推，不斷從新記錄點的相鄰未被走過頂點中 ... 2021iThome鐵人賽 0 SoftwareDevelopment 資料結構與演算法，使用JavaScript與Python系列第 33篇 【Day33】[演算法]-深度優先搜尋DFS與廣度優先搜尋BFS 13th鐵人賽 alogrithm 演算法 javascript python Frank 2021-10-1401:21:15775瀏覽 深度優先搜尋(Depth-FirstSearch,DFS)與廣度優先搜尋(Breadth-FirstSearch,BFS)，是可以用來走訪或搜尋樹節點與圖頂點的演算法，先前介紹的二元樹走訪就是使用上述方法走訪各節點，這邊以圖結構來介紹。

樹的走訪可以參考此篇。

下面相鄰串列構成的圖來示範搜尋 圖的介紹可以參考此篇。

深度優先搜尋DFS 先選定一個頂點開始走訪，接著從此頂點相鄰未被走過的頂點中，擇一走訪標示為記錄點，以此類推，不斷從新記錄點的相鄰未被走過頂點中尋找。

若新紀錄點的相鄰頂點都被走過，則退回前一個紀錄點，繼續從未被走過頂點中尋找。

深度優先可以利用堆疊(Stack)的方式來處理。

堆疊的介紹可以參考此篇。

廣度優先搜尋BFS 先選定一個頂點開始走訪，逐一走過此頂點相鄰未被走過的頂點，若相鄰頂點都被走過，再從走訪過的頂點中擇一為新記錄點，逐一走過新記錄點相鄰未被走過的頂點，以此類推。

廣度優先可以利用佇列(Queue)的方式來處理。

佇列的介紹可以參考此篇。

JavaScript classGraph{ constructor(){ this.adjacencyList={} } //新增頂點 addVertex(vertex){ if(!this.adjacencyList[vertex]){ this.adjacencyList[vertex]=[] }else{ return'頂點已存在'; } } //新增邊 addEdge(vertex1,vertex2){ if(this.adjacencyList[vertex1]){ if(this.adjacencyList[vertex2]){ this.adjacencyList[vertex1].push(vertex2) this.adjacencyList[vertex2].push(vertex1) }else{ return'第二項頂點不存在'; } }else{ return'第一項頂點不存在'; } } //刪除頂點 removeVertex(vertex){ if(this.adjacencyList[vertex]){ this.adjacencyList[vertex].forEach(function(item){ this.removeEdge(vertex,item) deletethis.adjacencyList[vertex] }); }else{ return'此頂點已不存在'; } } //刪除邊 removeEdge(vertex1,vertex2){ if(this.adjacencyList[vertex1]){ if(this.adjacencyList[vertex2]){ this.adjacencyList[vertex1]=this.adjacencyList[vertex1].filter( (vertex)=>vertex!==vertex2 ) this.adjacencyList[vertex2]=this.adjacencyList[vertex2].filter( (vertex)=>vertex!==vertex1 ) }else{ return'第二項頂點已不存在'; } }else{ return'第一項頂點已不存在'; } } printGraph(){ console.log(this.adjacencyList) } //廣度優先 bfs(start){ constqueue=[start]; constresult=[]; constvisited={}; visited[start]=true; letcurrentVertex; while(queue.length){ currentVertex=queue.shift(); result.push(currentVertex); this.adjacencyList[currentVertex].forEach(neighbor=>{ if(!visited[neighbor]){ visited[neighbor]=true; queue.push(neighbor); } }); } returnresult; } //深度優先 dfs(start){ constresult=[]; conststack=[start]; constvisited={}; visited[start]=true; letcurrentVertex; while(stack.length){ currentVertex=stack.pop(); result.push(currentVertex); this.adjacencyList[currentVertex].forEach(neighbor=>{ if(!visited[neighbor]){ visited[neighbor]=true; stack.push(neighbor); } }); } returnresult; } } letgraph=newGraph(); graph.addVertex('A'); graph.addVertex('B'); graph.addVertex('C'); graph.addVertex('D'); graph.addVertex('E'); graph.addVertex('F'); graph.addEdge('A','B'); graph.addEdge('A','D'); graph.addEdge('A','E'); graph.addEdge('B','C'); graph.addEdge('D','E'); graph.addEdge('E','F'); graph.addEdge('E','C'); graph.printGraph(); //{ //A:["B","D","E"], //B:["A","C"], //C:["B","E"], //D:["A","E"], //E:["A","D","F","C"], //F:["E"] //} console.log(graph.bfs('A')) //["A","B","D","E","C","F"] console.log(graph.dfs('A')) //["A","E","C","F","D","B"] console.log(graph.dfs('B')) //["B","C","E","F","D","A"] console.log(graph.dfs('C')) //["C","E","F","D","A","B"] console.log(graph.dfs('D')) //["D","E","C","B","F","A"] console.log(graph.dfs('E')) //["E","C","B","F","D","A"] console.log(graph.dfs('F')) //["F","E","C","B","D","A"] Python #Graph graph={ 'A':["B","D","E"], 'B':["A","C"], 'C':["B","E"], 'D':["A","E"], 'E':["A","D","F","C"], 'F':["E"] } defbfs(graph,start): queue=[] queue.append(start) result=[] visited=set() visited.add(start) while(len(queue)>0): currentVertex=queue.pop(0) result.append(currentVertex) forneighboringraph[currentVertex]: ifneighbornotinvisited: queue.append(neighbor) visited.add(neighbor) returnresult defdfs(graph,start): stack=[] result=[] stack.append(start) visited=set() visited.add(start) while(len(stack)>0): currentVertex=stack.pop() result.append(currentVertex) forneighboringraph[currentVertex]: ifneighbornotinvisited: stack.append(neighbor) visited.add(neighbor) returnresult print(bfs(graph,'A')) #['A','B','D','E','C','F'] print(dfs(graph,'A')) #['A','E','C','F','D','B'] 留言 追蹤 檢舉 上一篇 【Day32】[演算法]-內插搜尋法InterpolationSearch 下一篇 【Day34】[演算法]-費波那契數列FibonacciSequence 系列文 資料結構與演算法，使用JavaScript與Python 共35篇 目錄 RSS系列文 訂閱系列文 19人訂閱 31 【Day31】[演算法]-二分搜尋法BinarySearch 32 【Day32】[演算法]-內插搜尋法InterpolationSearch 33 【Day33】[演算法]-深度優先搜尋DFS與廣度優先搜尋BFS 34 【Day34】[演算法]-費波那契數列FibonacciSequence 35 【Day35】[演算法]-常見的演算法策略AlgorithmicPatterns 完整目錄 尚未有邦友留言 立即登入留言 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) 科學家與研究生的關係研究篇 30天Python自學:Day01 [Day??]2021iThome鐵人賽-頒獎典禮@2022.01.08‧輔仁大學 印表機維修五種常見故障，若遇到問題就能先自己排除了 一週點數排行 更多點數排行 海綿寶寶(antijava) Gary(mosbbs) raytracy(raytracy) 一級屠豬士(hitomitanaka) Samuel(kuanyu) ccenjor(ccenjor) 居然解出來了(partyyaya) horace_work(horace_work) 純真的人(jer5173) souda(souda) × At 輸入對方的帳號或暱稱 Loading 找不到結果。

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