簡介top

廣度優先搜尋 (Breadth-First Search，縮稱為BFS) 是用於圖形或樹狀結構的一種搜尋演算法，每次搜尋的方向是以資料結構的廣度為主，當該層節點都搜尋完畢還是搜尋不到目標，則進入到更深一層的節點繼續搜尋。

實作方式可用佇列(Queue)結構來做搜尋可走訪的記錄。

圖形結構範例top

考慮以下圖形結構，以BFS的走訪結果會是如何?

現在我們以1這個節點作為出發點並且輸出了1，那麼現在能走的節點分別有2、3、4，因此Queue中我們就存放進了這些節點，如下圖:

由於Queue先進先出的特性，因此我們Pop了2這個節點並輸出，然後2這個節點有5這個節點可以走訪，因此須把5這個節點Push進Queue，變成如下圖:

接著換Pop 3這個節點，而3這個節點有6這個節點可以走訪，因此須把6這個節點Push進Queue，變成如下圖:

接下來的每一步再繼續依照Queue的特性輸出，即可得到最終BFS走訪的結果，如下圖:

Last updated: June 24, 2023