上一回提到廣度優先搜尋的步驟是檢查圖中節點，並將與其相連的節點放入佇列中，再一一檢查。

光是這樣的文字描述，可能感覺只是線性地檢查所有節點，但其實廣度優先搜尋的重點在於它是從一個節點開始，放射狀、逐層向外的搜尋。

從起始的節點開始，它所有鄰居(neighbors，指相鄰的節點)算是第一層，要先搜尋完第一層所有的節點後，才開始搜尋鄰居的鄰居，也就是第二層的節點，所以整個搜尋會從起點向外層層擴展。

如果不是這樣一層一層搜尋，就可能會出現內層還沒搜尋完，就搜尋外層的錯誤，這樣會造成什麼問題呢？

借立可帶

假設毛豆同學今天忘了帶立可帶，想要跟同學借，並且希望能借他的同學座位離他越近越好。所以毛豆就從跟他座位直接相連的前、後、左、右四位同學問起。如果這四位同學都沒有，他們再跟他們的前後左右的同學詢問。

如果毛豆問完右邊的A同學，A同學沒等毛豆問其他人，就立馬再問他右邊的Q同學，發現Q同學有立可帶。可是其實毛豆左邊的B同學就有立可帶，但因為先問了第二層的同學，所以最終雖然有借到立可帶，但並不是距離毛豆最近的選項。

也就是說，如果不是第一層的鄰居搜尋完再搜尋第二層，可能發生找到的路徑並非最短路徑的問題。為了要避免這種情況，我們要利用佇列(queue)這種結構。

佇列

佇列是一種線性的資料結構。它的名稱queue也是排隊的意思，現實生活中在排隊結帳時，先開始排的人會先結帳離開，想要排隊只能從隊伍最後排起。

資料結構的佇列跟排隊一模一樣，資料從前端刪除，後端加入，所以先加入的資料一定會先刪除。跟同樣是線性結構的堆疊相比，佇列是先進先出(FIFO)的資料結構；堆疊則是後進先出(LIFO)。

先進先出的這個特性，就確保了廣度優先搜尋會找到正確答案。

今天毛豆想要借立可帶的第一步，就是先將他四周的ABCD同學加入佇列中，問了A同學發現沒有，就把A同學的鄰居OPQ同學加入佇列中，也就是排隊在BCD之後。因為佇列運作的方式，一定會先檢查完BCD才會輪到後面加入的同學，所以絕對不會出現坐比較遠的同學先被詢問的情況。

無限迴圈問題

除了搜尋順序外，操作廣度優先搜尋時我們可能還會碰到另一個問題，就是把已經檢查過的節點又加入了佇列。

例如當毛豆問完A同學後，就要把A同學的鄰居加入佇列，可是這麼做的時候又會把毛豆算進去，因為他們互為鄰居，會不斷把對方加入佇列。

當發生這樣的情形時，不但會浪費資源搜尋已經檢查過的節點，而且搜尋會陷入無限迴圈。所以通常會用一些方式來標示已經檢查過的節點，例如將檢查過的節點存入一陣列，以避免重複檢查。

廣度優先搜尋是一種會徹底搜尋整張圖的演算法，最壞情況得經過每個邊並檢查每個節點，所以執行時間是O(|V|+|E|)，其中|V|是節點的數目，|E|是邊的數目。