圖算法——廣度優(yōu)先搜索 （breadth-first search旷偿，BFS）狸捅。廣度優(yōu)先搜索讓你能夠找出兩樣?xùn)|西之間的最短距離累提。
圖
你經(jīng)常要找出最短路徑，這可能是前往朋友家的最短路徑朽褪，也可能是國際象棋中把對方將死的最少步數(shù)无虚。解決最短路徑問題的算法被稱為廣度優(yōu)先搜索 。
圖是什么?
圖由節(jié)點和邊組成嗤堰。一個節(jié)點（node）可能與眾多節(jié)點（edge）直接相連度宦，這些節(jié)點被稱為鄰居
廣度優(yōu)先搜索可回答兩類問題。
第一類問題：從節(jié)點A出發(fā)离唬，有前往節(jié)點B的路徑嗎？
第二類問題：從節(jié)點A出發(fā)戚哎，前往節(jié)點B的哪條路徑最短嫂用？
在你看來，一度關(guān)系勝過二度關(guān)系甘畅，二度關(guān)系勝過三度關(guān)系实夹，以此類推亮航。因此匀们，你應(yīng)先在一度關(guān)系中搜索，確定其中沒有芒果銷售商后重抖，才在二度關(guān)系中搜索祖灰。廣度優(yōu)先搜索就是這樣做的！在廣度優(yōu)先搜索的執(zhí)行過程中恨统，搜索范圍從起點開始逐漸向外延伸三妈，即先檢查一度關(guān)系，再檢查二度關(guān)系悠鞍。
隊列
隊列只支持兩種操作：入隊 和出隊 模燥。
隊列是一種先進先出 （First In First Out掩宜，F(xiàn)IFO）的數(shù)據(jù)結(jié)構(gòu)
實現(xiàn)圖
首先锭亏，需要使用代碼來實現(xiàn)圖硬鞍。圖由多個節(jié)點組成。
的一種結(jié)構(gòu)讓你能夠表示這種關(guān)系锅减，它就是散列表 伐坏！
散列表讓你能夠?qū)㈡I映射到值。在這里每瞒，你要將節(jié)點映射到其所有鄰居纯露。
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)緊要
無向圖 （undirected graph）沒有箭頭，直接相連的節(jié)點互為鄰居贷掖。
實現(xiàn)算法
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = [] # 這個數(shù)組用于記錄檢查過的人
while search_queue:
person = search_queue.popleft()
if person not in searched:
# 僅當(dāng)這個人沒檢查過時才檢查
if person_is_seller(person):
print person +" is a mango seller!"
return True
else:
search_queue += graph[person]
searched.append(person) # 將這個人標(biāo)記為檢查過
return False search("you")
渴语，廣度優(yōu)先搜索的運行時間為O (人數(shù) + 邊數(shù))，這通常寫作O (V + E )屠升，其中V 為頂點（vertice）數(shù)狭郑，E 為邊數(shù)。
拓?fù)渑判?/h2>
如果任務(wù)A依賴于任務(wù)B翰萨，在列表中任務(wù)A就必須在任務(wù)B后面。這被稱為拓?fù)渑判颉?/p>
樹是一種特殊的圖阿蝶，其中沒有往后指的邊黄绩。
如果任務(wù)A依賴于任務(wù)B翰萨，在列表中任務(wù)A就必須在任務(wù)B后面。這被稱為拓?fù)渑判颉?/p>
