摘要：解決最短路徑問題的算法被稱為廣度優(yōu)先搜索。廣度優(yōu)先搜索算法最早由年在如何從迷宮中尋找出路這一問題中提出。廣度優(yōu)先搜索讓你能夠找出兩樣?xùn)|西之間的最短距離。使用廣度優(yōu)先搜索解決問題。

你經(jīng)常需要解決最短路徑問題(shorterst-path problem)。解決最短路徑問題的算法被稱為廣度優(yōu)先搜索。廣度優(yōu)先搜索算法最早由Edward F. Moore 1959年在“如何從迷宮中尋找出路”這一問題中提出。

廣度優(yōu)先搜索讓你能夠找出兩樣?xùn)|西之間的最短距離。使用廣度優(yōu)先搜索可以:

編寫國際跳棋AI,計算最少走多少步就可獲勝;

編寫拼寫檢查器,計算最少編輯多少個地方就可將錯拼的單詞改成正確的單詞,如將READED改為READER需要編輯一個地方;

根據(jù)你的人際關(guān)系網(wǎng)絡(luò)找到關(guān)系最近的醫(yī)生。

要解決最短路徑問題，需要兩個步驟。

使用圖來建立問題模型。

使用廣度優(yōu)先搜索解決問題。

圖用于模擬不同的東西是如何相連的。圖由節(jié)點(node)和邊(edge)組成。一個節(jié)點可能與眾多節(jié)點直接相連,這些節(jié)點被稱為鄰居。樹是一種特殊的圖,其中沒有往后指的邊。

在圖中，邊用來表示節(jié)點之間的關(guān)系，若關(guān)系是有方向的，則圖為有向圖(directed graph)，此時圖中的邊有箭頭。若關(guān)系沒有方向，則圖為無向圖(undirected graph),此時圖中的邊沒有箭頭，直接相連的節(jié)點互為鄰居。

如上圖是有向圖，Rama是Alex的鄰居。

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

第一類問題:從節(jié)點A出發(fā),有前往節(jié)點B的路徑嗎?

第二類問題:從節(jié)點A出發(fā),前往節(jié)點B的哪條路徑最短?

兩類問題并沒有本質(zhì)區(qū)別，在實現(xiàn)層面僅僅第二類需要攜帶路徑的信息，因為最終通常需要返回這個路徑。

示例：假設(shè)你經(jīng)營著一個芒果農(nóng)場,需要尋找芒果銷售商,以便將芒果賣給他。在Facebook,你與芒果銷售商有聯(lián)系嗎?為此,你可在朋友中查找。

算法原理：
（1）創(chuàng)建一個朋友名單。
（2）依次檢查名單中的每個人,看看他是否是芒果銷售商。
（3）假設(shè)你沒有朋友是芒果銷售商,那么你就必須在朋友的朋友中查找。檢查名單中的每個人時,你都將其朋友加入名單。

若找到，則表示你與芒果銷售商有聯(lián)系；由于在廣度優(yōu)先搜索的執(zhí)行過程中,搜索范圍從起點開始逐漸向外延伸,即先檢查一度關(guān)系,再檢查二度關(guān)系，我們找到的芒果銷售商也是關(guān)系最近的。

執(zhí)行過程中，一度關(guān)系在二度關(guān)系之前加入查找名單，所以我們優(yōu)先檢查一度關(guān)系，然后才到二度，依次進行。這需要存儲名單的數(shù)據(jù)結(jié)構(gòu)有“先進先出”的特性，這種數(shù)據(jù)結(jié)構(gòu)就是隊列(queue)。

類似于棧,隊列也是一種操作受限的數(shù)據(jù)結(jié)構(gòu)，你不能隨機地訪問隊列中的元素。隊列只支持兩種操作:入隊和出隊。

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

使用散列表存儲每個節(jié)點與鄰近節(jié)點關(guān)系。

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"] = []

算法的工作原理：

一點需要注意：檢查一個人之前,要確認(rèn)之前沒檢查過他,這很重要，因為有可能會導(dǎo)致無限循環(huán)。

完整算法如下：

from collections import deque

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"] = []


def person_is_seller(name):
    return name[-1] == "m"

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if not person in searched:
            if person_is_seller(person):
                print(person + " is a mango seller!")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False

search("you")

算法的時間復(fù)雜度：O(V + E)，其中V為頂點(vertice)數(shù),E為邊數(shù)。

請繼續(xù)關(guān)注我的公眾號文章