iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 8
0
自我挑戰組

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

[Data Structure][Graph] - Traversal - BFS

圖形的走訪 Traversal

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

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

  • BFS
    走訪的順序為將某個頂點視為起點,接著拜訪和起點相鄰的所有頂點,再走訪與起點相鄰的頂點的相鄰頂點,也就是在走訪更外一層的意思,持續更外層找相鄰頂點,直到所有連通頂點都被走訪過了。
    • 由內而外,一層一層走訪的概念可以使用佇列結構。

    • 以下圖為例子
      https://ithelp.ithome.com.tw/upload/images/20181022/20112438feRq7IGozU.jpg

    • 其中一組拜訪順序為

A [B,C,D] [G,H,F,E] [I]
起點 第1層 第2層 第3層
動作說明 Queue 已走訪的頂點
(0) 初始狀態 (前) (尾) 無頂點
(1) 走訪頂點A,Enquene(A) A A
(2) Dequeue得到A,將與A相鄰且未被拜訪的頂點(B、C、D)逐一拜訪,並且Enqueue B、C、D A、B、C、D
(3) Dequeue得到B,B沒有與任何頂點相鄰 C、D A、B、C、D
(4) Dequeue得到C,C與G、H相鄰且未被拜訪,所以Enqueue (G)、(H) D、G、H A、B、C、D、G、H
(5) Dequeue得到D,D與E、F相鄰且未被拜訪,所以Enqueue (E)、(F) G、H、E、F A、B、C、D、E、G、H、E、F
(6) Dequeue得到G,G與C、H、F相鄰,但都被拜訪過了 H、E、F A、B、C、D、E、G、H、E、F
(7) Dequeue得到H,G與C、G、F相鄰,但都被拜訪過了 E、F A、B、C、D、E、G、H、E、F
(8) Dequeue得到E,E與D相鄰,但被拜訪過了 F A、B、C、D、E、G、H、E、F
(9) Dequeue得到F,F與G、I相鄰,但I沒被拜訪過,所以Enqueue (I) I A、B、C、D、E、G、H、E、F、I
(10) Dequeue得到I,I與F相鄰,但被拜訪過了 A、B、C、D、E、G、H、E、F、I
(11) Queue 為空,停止

參考

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


上一篇
[Data Structure][Graph] - Representation
下一篇
[Data Structure][Graph] - Traversal - DFS
系列文
學習資料結構30天30

尚未有邦友留言

立即登入留言