【引言】我們生活中都會(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é)果是：
