iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 9
0
自我挑戰組

學習資料結構30天系列 第 9

[Data Structure][Graph] - Traversal - DFS

圖形的走訪 Traversal

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

走訪的順序分為: 廣度優先 (Breadth First Search)深度優先 (Depth First Search)

  • DFS
    是從某一起點A開始,接著選擇一個與起點相鄰的頂點B,接著選擇與B點相鄰的起點,一直深度優先走訪,直到找到某一個頂點C的相鄰頂點都被走訪過,就回到頂點C上一個走訪的點,繼續做深度優先走訪。

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

    演算法

    將起始頂點(A) Push入Stack
    若Stack不是空的,重複迴圈
    -> 從Stack中Pop出一個頂點 (B)
    -> 若頂點(B)沒有被走訪過,就走訪(B),並將所有與頂點(B)相鄰且沒有被走訪過的Push進Stack
    迴圈結束
    
    • 同樣以下圖為例子
      https://ithelp.ithome.com.tw/upload/images/20181022/20112438feRq7IGozU.jpg

    • 其中一組拜訪順序為
      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為空,停止

參考

細談資料結構 第六版
ISBN 978-986-312-014-8


上一篇
[Data Structure][Graph] - Traversal - BFS
下一篇
[Data Structure][Graph] -Spanning Tree !
系列文
學習資料結構30天30

尚未有邦友留言

立即登入留言