【引言】我們生活中都會(huì)有過“找人”的經(jīng)歷。比如，我們想簡(jiǎn)單的找一個(gè)醫(yī)生來咨詢一些事情，或者找一個(gè)律師或者是老師。我們會(huì)怎么找呢？怎么才能找到呢？我們往往希望找到的這個(gè)人是跟我們關(guān)系最近的那一個(gè)，或者是朋友，或者是朋友的朋友，如果是朋友的朋友的朋友，我們的信任感或者說覺得這個(gè)關(guān)系就不那么牢靠了。這個(gè)過程就是一個(gè)搜索的過程，而我們的人際關(guān)系網(wǎng)就是一個(gè) 圖。
廣度優(yōu)先搜索就是一個(gè)首先搜索自己身邊最近的人，如果沒有，我們?cè)贁U(kuò)大搜索范圍的一種搜索方法。
算法過程
圖
我們可以想象，我們?cè)谡胰说倪^程，實(shí)際上就是我們搜索我們?nèi)穗H關(guān)系關(guān)系網(wǎng)中的人的過程，而這個(gè)人際關(guān)系網(wǎng)，就是由一個(gè)個(gè)朋友、朋友的朋友……來構(gòu)建的，我們可以把這種關(guān)系看做是一個(gè) 圖：
圖是有方向的，箭頭的方向表示的是從屬關(guān)系，被指的人是前者的朋友，其實(shí)應(yīng)該是互相指的雙向箭頭，但是因?yàn)槲业拇嬖?，我只能通過一個(gè)人來找到他的朋友，所以有了單向的方向。即使是這樣，也會(huì)存在一個(gè)人同時(shí)是幾個(gè)人的朋友這種情況，可能會(huì)出現(xiàn)一個(gè)環(huán)，如上圖，這個(gè)環(huán)也可能是來回循環(huán)的。
廣度優(yōu)先搜索
廣度優(yōu)先搜索，顧名思義，就是盡量的先 廣泛 的來搜索。
比如，我要買房子，我就要要找到我身邊人際網(wǎng)中的一個(gè)搞房地產(chǎn)的人。我該怎么辦呢？按照廣度優(yōu)先搜索的話，我應(yīng)該這么辦：
首先，我遍尋我身邊的朋友，也就是直接跟我是朋友的人，看看他們是不是搞房地產(chǎn)的人，如果有搞房地產(chǎn)的人，我就算是以一個(gè)比較短的路徑，一個(gè)比較短的時(shí)間找到了我所需要的人（黑圈中的人）：
然后，當(dāng)我遍尋我身邊直接的朋友沒有找到搞房地產(chǎn)的人的時(shí)候，此時(shí)我就知道，我身邊朋友這個(gè)范圍已經(jīng)找不到了，此時(shí)我就要增加我的搜索范圍，來找我的朋友的朋友了（紅圈之內(nèi)，黑圈之外）：
如果我找到了，那么這個(gè)搜索過程就結(jié)束了，如果沒有找到，我再繼續(xù)搜索朋友的朋友的朋友……，一次次的增加搜索的范圍。
這就是廣度優(yōu)先搜索的過程，所謂廣度，就是每一次搜索的范圍要盡量的廣泛，比如，我第一次搜索，范圍就是最廣泛的，我 遍尋 了我身邊所有的 朋友；第二次搜索，我 遍尋 了我身邊 朋友的朋友 ；如果有第三次，我就繼續(xù)遍尋我朋友的朋友的朋友……，很幸運(yùn)，我在我的朋友的朋友中，找到了我要找的人，這樣就以廣度優(yōu)先的搜索方式完成了我找人的目的！
具體的實(shí)現(xiàn)邏輯是，我借助一個(gè)隊(duì)列，首先把我所有的朋友加入隊(duì)列，從隊(duì)列頭一個(gè)個(gè)的來查看我的朋友是不是我要找的人，如果某個(gè)朋友不是我要找的，那么我就把他的朋友繼續(xù)加入隊(duì)列的末尾，把他從隊(duì)列頭中拿走，繼續(xù)的查看隊(duì)列中第二個(gè)朋友，重復(fù)這個(gè)過程，直到我的隊(duì)列中的所有人都被我查看過了，沒有找到，那我身邊就沒有這樣的人。
算法實(shí)現(xiàn)
#coding:utf-8
# 引入隊(duì)列，實(shí)際上用數(shù)組也是完全沒問題的，有這個(gè)就用這個(gè)
from collections import deque
# 廣度優(yōu)先搜索的過程
def breadth_first_search(career, name):
search_queue = deque()
search_queue += friends[name]
searched = []
# 只要待查找的數(shù)組不為空，就一直搜索下去
while search_queue:
# 從隊(duì)列的頭找出一個(gè)朋友
person = search_queue.popleft()
# 如果這個(gè)朋友沒有在已查找的數(shù)組中，就確認(rèn)他的身份（為了防止幾個(gè)人都互相是朋友的死循環(huán)，如果查過這個(gè)人，就不再查了）
if person not in searched:
# 如果這個(gè)人是要找的人，直接返回
if careers[person] == career:
return person
# 如果這個(gè)人不是要找的人，就把這個(gè)人的朋友放入帶查找的隊(duì)列的末尾
else:
search_queue.extend(friends[person])
searched.append(person)
# 如果關(guān)系網(wǎng)上所有的人中都沒有要找的人，就直接返回沒有
return False
# 構(gòu)建人物的基本職業(yè)信息以及朋友網(wǎng)
careers = {"我": "屌絲",
"呂志安": "醫(yī)生",
"李小飛": "律師",
"林連杰": "老總",
"王洲": "房地產(chǎn)",
"王忠義": "護(hù)士",
"封趙蒙": "保險(xiǎn)"}
friends = {"我": ["呂志安", "李小飛", "林連杰"],
"呂志安": ["封趙蒙"],
"李小飛": ["王洲", "王忠義"],
"林連杰": [],
"王洲": ["王忠義"],
"王忠義": [],
"封趙蒙": []}
# 進(jìn)行廣度優(yōu)先搜索，來查找 我 的身邊做 房地產(chǎn) 的朋友
searched_man = breadth_first_search("房地產(chǎn)", "我")
if searched_man:
print("你身邊做“房地產(chǎn)”的朋友是： {}".format(searched_man))
else:
print("你身邊沒有做“房地產(chǎn)”的朋友")
結(jié)果是：
