小朋友們好，大朋友們好！

我是貓妹，一名愛上Python編程的小學生。

和貓妹學Python，一起趣味學編程。

今日主題

咱們之前分別學習了圖的基本概念，和圖的深度優(yōu)先遍歷算法dfs。

你學會了嗎？

咱們今天要學習圖的另一種遍歷方法：

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷(Breadth First Search)是一種圖的遍歷算法，它從一個頂點出發(fā)，沿著與該頂點相鄰的所有邊進行遍歷，直到無法繼續(xù)為止。

然后再回溯到上一個頂點，沿著與該頂點不相鄰的其他邊進行遍歷，直到無法繼續(xù)為止。

重復這個過程，直到所有頂點都被訪問過為止。

深度優(yōu)先和廣度優(yōu)先

分別對下圖進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷

深度優(yōu)先搜索(Depth First Search)

先選擇一條路一直往前走，走到盡頭后，就返回到上一個交叉路口選擇另一條沒走過的路。

一直重復，這樣就能走完所有的地點。

像不像老鼠走迷宮，一條路一條路地嘗試？

深度優(yōu)先搜索的一種實現：

廣度優(yōu)先搜索（Breadth First Search)

從頂點開始，先訪問距離起始頂點長度為1的頂點，再訪問距離起始頂點長度為2的頂點。

如此反復。

廣度優(yōu)先搜索的一種實現：

廣度優(yōu)先代碼實現

假設從0開始，實現上圖的廣度優(yōu)先遍歷。

首先訪問距離頂點0長度為1的結點{1,2,3}

然后訪問距離頂點0長度為2的頂點{4,6}，

然后訪問長度為3的頂點{5}，

最后訪問長度為4的頂點{7}。

具體該怎么實現呢？

這里需要用到一個雙端隊列。

雙端隊列

雙端隊列(Deque)是一種允許我們同時從前端和后端添加和刪除元素的特殊隊列，它是隊列和棧的結合體。?

相對于普通隊列，雙端隊列的入隊和出隊操作在兩端都可進行。

雙端隊列初始狀態(tài)為{0}。

我們訪問0后，0從隊首出隊，同時用集合記錄0已經被訪問。將0的鄰接頂點{1,2,3}從對尾入隊，這都是距離起始頂點長度為1的節(jié)點。

然后1從隊首出隊，同時用集合記錄1已經被訪問。將1的鄰接頂點從對尾入隊，這都是距離起始頂點長度為2的節(jié)點。（也可能是2或3，看123入隊的順序）。

依次訪問2和3，并用集合記錄以訪問，其鄰接頂點分別從隊尾入隊。

如上反復，知道雙端隊列為空。

參考代碼：

1行：deque 是Python標準庫 collections 中的一個類，實現了兩端都可以操作的隊列，相當于雙端隊列，與Python的基本數據類型列表很相似。

15行：將起始頂點的鄰接頂點添加到隊列中。

16行：將起始頂點放入以訪問過的結合中。

17行：如果隊列非空，則繼續(xù)訪問。

18行：從隊首彈出元素，進行訪問。

20~23行：判斷出隊元素的鄰接頂點沒有被訪問，放入隊列尾部。

你學會了嗎？

好了，我們今天就學到這里吧！

如果遇到什么問題，咱們多多交流，共同解決。

我是貓妹，咱們下次見！