[Data Structure][Graph] - Traversal - DFS - iT 邦幫忙

圖形的走訪Traversal 指從某個頂點作為起點，依照某種順序，一個一個拜訪(visit)所有能到達的頂點。

走訪的順序分為: 廣度優先(Breadth First Search) ... 2019iT邦幫忙鐵人賽 DAY 9 0 自我挑戰組 學習資料結構30天系列第 9篇 [DataStructure][Graph]-Traversal-DFS 2019鐵人賽 dfs smalloneeeee 2018-10-2322:44:113313瀏覽 圖形的走訪Traversal 指從某個頂點作為起點，依照某種順序，一個一個拜訪(visit)所有能到達的頂點。

走訪的順序分為:廣度優先(BreadthFirstSearch)和深度優先(DepthFirstSearch) DFS 是從某一起點A開始，接著選擇一個與起點相鄰的頂點B，接著選擇與B點相鄰的起點，一直深度優先走訪，直到找到某一個頂點C的相鄰頂點都被走訪過，就回到頂點C上一個走訪的點，繼續做深度優先走訪。

頂點的選擇是使用LIFO的方式管理，所以可以用Stack結構。

演算法 將起始頂點(A)Push入Stack 若Stack不是空的，重複迴圈 ->從Stack中Pop出一個頂點(B) ->若頂點(B)沒有被走訪過，就走訪(B)，並將所有與頂點(B)相鄰且沒有被走訪過的Push進Stack 迴圈結束 同樣以下圖為例子 其中一組拜訪順序為 A,B,C,G,F,D,E,I,H 拜訪頂點的時機:將頂點從堆疊中POP出 動作說明 Stack 已走訪的頂點 (0)初始狀態 (頂端)(尾) (1)起點為頂點A，Push(A) A 無頂點 (2)Pop(A)，走訪頂點A。

將未走訪且與A相鄰的點Push，Push(B、C) B、C A (3)Pop(B)，走訪頂點B，沒有頂點與B相鄰 C A、B (4)Pop(C)，走訪頂點C。

將未走訪且與C相鄰的點Push，Push(G、H) G、H A、B、C (5)Pop(G)，走訪頂點G。

將未走訪且與G相鄰的點Push，Push(F、H) F、H(與G相鄰)、H(與C相鄰) A、B、C、G (6)Pop(F)，走訪頂點F。

將未走訪且與F相鄰的點Push，Push(D、I) D、I、H、H A、B、C、G、F (7)Pop(D)，走訪頂點F。

將未走訪且與D相鄰的點Push，Push(E) E、I、H、H A、B、C、G、F、D (8)Pop(E)，走訪頂點E。

頂點D與B相鄰但已經走訪過 I、H、H A、B、C、G、F、D、E (9)Pop(I)，走訪頂點I。

頂點F與I相鄰但已經走訪過 H、H A、B、C、G、F、D、E、I (10)Pop(H)，走訪頂點H。

頂點C和G都與I相鄰但已經走訪過 H A、B、C、G、F、D、E、I、H (11)Pop(H)，H已經走訪過了 空 A、B、C、G、F、D、E、I、H (12)Stack為空，停止 參考 細談資料結構第六版 ISBN978-986-312-014-8 留言 追蹤 檢舉 上一篇 [DataStructure][Graph]-Traversal-BFS 下一篇 [DataStructure][Graph]-SpanningTree! 系列文 學習資料結構30天 共30篇 目錄 RSS系列文 訂閱系列文 20人訂閱 26 [DataStructure][Sort]-SelectionSort 27 [DataStructure][Sort]-InsertionSort 28 [DataStructure][Sort]-MergeSort 29 [DataStructure][Sort]-QuickSort 30 [DataStructure][Search]-BinarySearch 完整目錄 尚未有邦友留言 立即登入留言 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}} 關閉