摘要：解決最短路徑問題的算法被稱為廣度優(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)先搜索可以:

編寫國(guó)際跳棋AI,計(jì)算最少走多少步就可獲勝;

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

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

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

使用圖來(lái)建立問題模型。

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

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

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

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

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

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

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

兩類問題并沒有本質(zhì)區(qū)別，在實(shí)現(xiàn)層面僅僅第二類需要攜帶路徑的信息，因?yàn)樽罱K通常需要返回這個(gè)路徑。

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

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

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

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

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

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

使用散列表存儲(chǔ)每個(gè)節(jié)點(diǎn)與鄰近節(jié)點(diǎn)關(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"] = []

算法的工作原理：

一點(diǎn)需要注意：檢查一個(gè)人之前,要確認(rèn)之前沒檢查過他,這很重要，因?yàn)橛锌赡軙?huì)導(dǎo)致無(wú)限循環(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")

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

請(qǐng)繼續(xù)關(guān)注我的公眾號(hào)文章