數(shù)據(jù)結(jié)構(gòu)和算法
基于《算法圖解》—Aditya Bhargava 和《數(shù)據(jù)結(jié)構(gòu)》—嚴蔚敏

第6章廣度優(yōu)先搜索

6.1 簡介
廣度優(yōu)先搜索—breadth-first search，BFS.
主要內(nèi)容圖和隊列。
廣度優(yōu)先搜索能讓你能夠找出兩樣東西之間的最短距離，比如：編寫國際跳棋AI(Artificial Intelligence)，計算最少走多少步可以獲勝；或者根據(jù)你的人際關(guān)系網(wǎng)絡(luò)找到關(guān)系最近的醫(yī)生。

需要兩個步驟：

（1）使用圖來建立問題模型。
（2）使用廣度優(yōu)先搜索解決問題。

6.2 什么是圖
圖由節(jié)點和邊組成。一個節(jié)點可能與眾多節(jié)點直接相連，這些節(jié)點被稱為鄰居。

6.3 廣度優(yōu)先搜索
廣度優(yōu)先搜索是一種用于圖的查找算法，可幫助回答兩類問題：

• 第一類問題：從節(jié)點A出發(fā)，有前往節(jié)點B的路徑嗎？
• 第二類問題：從節(jié)點A出發(fā)，前往節(jié)點B的哪條路徑最短？

假設(shè)你經(jīng)營著一個芒果農(nóng)場，需要尋找芒果銷售商，以便將芒果賣給他。為此，你可在朋友中查找。

首先創(chuàng)建一個朋友名單，然后依次檢查名單中的每個人，是否是芒果銷售商：

假設(shè)你沒有朋友是芒果銷售商，那么你就必須在朋友的朋友中查找。

檢查名單中的每個人時，你都將其朋友加入名單。

6.3.1 查找最短路徑
一度關(guān)系勝過二度關(guān)系，二度關(guān)系勝過三度關(guān)系，以此類推。

廣度優(yōu)先搜索不僅查找從A到B的路徑，而且找到的是最短的路徑。

只有按添加順序查找時，才能實現(xiàn)這樣的目的。

隊列(queue)：實現(xiàn)按添加順序進行檢查的數(shù)據(jù)結(jié)構(gòu)。

6.3.2 隊列
隊列能夠?qū)崿F(xiàn)按添加順序進行檢查的需求。
隊列不能隨機訪問，只能支持兩種操作：入隊和出隊。

先加入的元素將先出隊并被檢查。

隊列是一種先進先出(First In First Out)的數(shù)據(jù)結(jié)構(gòu)；
棧是一種后進先出(Last In First Out)的數(shù)據(jù)結(jié)構(gòu)。

6.4 實現(xiàn)圖
圖是由多個節(jié)點組成，需要使用代碼來實現(xiàn)圖。
每個結(jié)點都與鄰近結(jié)點相連，散列表可以很好的實現(xiàn)這種關(guān)系。

散列表將鍵映射到值，比如將你這個節(jié)點映射到所有鄰居。

表示這種映射關(guān)系的Python代碼如下，

graph = {} #前面提到Python中是用字典來實現(xiàn)散列表。{}表示生成空字典。 graph["you"] = ["alice", "bob", "claire"] #"you"被映射到了一個數(shù)組，因此graph["you"]是一個數(shù)組，包含了"you"的所有鄰居。

graph = {} graph["you"] = ["alice", "bob", "claire"] graph["bob"] = ["anuj", "peggy"] graph["alice"] = ["peggy"] graph["claire"] = ["thom", "jonny"] graph["anuj"] = [] graph["peggy"] = [] graph["thom"] = [] graph["jonny"] = [] #散列表是無序的，因此添加鍵-值對的順序不關(guān)緊要。

有向圖(directed graph)：有一個節(jié)點指向相鄰節(jié)點，單向關(guān)系。上圖中Anuj,Peggy,Thom,Jonny都沒有鄰居，因為他們沒有指向其他節(jié)點。

無向圖(undirected graph)：沒有箭頭，直接連接的節(jié)點互為鄰居。
下面兩圖等效：

6.5 實現(xiàn)算法
隊列實現(xiàn)原理

#首先使用函數(shù)deque來創(chuàng)建一個雙端隊列。 from collections import deque def search(name):search_queue = deque() #創(chuàng)建一個隊列search_queue += graph[name] #將鄰居都加入到這個搜索隊列中。searched = [] #這個數(shù)組用于記錄檢查過的人，避免無限循環(huán)。#進行對每個人進行檢查while search_queue: #只要隊列不為空，person = search_queue.popleft() #就取出其中的第一個人(左端)if person not in searched: #僅當這個人沒檢查過時才檢查if person_is_seller(person): #檢查此人是否是芒果銷售商print(person + "is a mango seller!")return Trueelse:search_queue += graph[person] #如果不是，將此人的朋友(相鄰節(jié)點)都加入搜索隊列。searched.append(person) #并將此人添加到以搜索過的列表，避免再次搜索此人。return False #如果到達這里，說明隊列中沒有芒果銷售商#假設(shè)以姓名結(jié)尾為m的人為芒果銷售商。 def person_is_seller(name):return name[-1] == 'm' #名字末尾為msearch("you") #函數(shù)調(diào)用

為什么要避免被重復搜索(檢查)：
上圖中Peggy既是Alice的朋友又是Bob的朋友，因此她將被加入隊列兩次；因此，搜索隊列將包含兩個Peggy。

檢查完一個人后，應(yīng)將其標記為已檢查，且不再檢查；如果不這樣做，就可能會導致無限循環(huán)。

因為搜索隊列將在包含你和包含Peggy之間反復切換，從而造成無限循環(huán)。

列表是有序的。如果任務(wù)A依賴于任務(wù)B，在列表中任務(wù)A就必須在任務(wù)B后面，這被稱為拓撲排序，使用它可根據(jù)圖創(chuàng)建一個有序表。

6.5.1 樹
樹是特殊的圖，其中沒有往后指的邊。

樹是圖的子集，樹都是圖，圖不一定是樹。

6.6 小結(jié)

• 隊列是先進先出。
• 棧是后進先出。
• 注意避免導致無限循環(huán)。

——持續(xù)修改完善中…

總結(jié)

以上是生活随笔為你收集整理的06-广度优先搜索:图、队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。