APP
Hello，大家好我叫是Dream呀，一個(gè)有趣的Python博主，小白一枚，多多關(guān)照 ?
入門須知：這片樂園從不缺乏天才，努力才是你的最終入場(chǎng)券！
最后，愿我們都能在看不到的地方閃閃發(fā)光，一起加油進(jìn)步
“一萬(wàn)次悲傷，依然會(huì)有Dream，我一直在最溫暖的地方等你”，唱的就是我！哈哈哈~
第六章：廣度優(yōu)先搜索
6.1圖簡(jiǎn)介
圖算法：廣度優(yōu)先搜索！
前往某一地點(diǎn)，需要的最短路徑被稱為是：最短路徑問題
解決最短路徑問題的算法被稱作：廣度優(yōu)先搜索
6.2圖是什么
圖模擬一組連接。圖由節(jié)點(diǎn)和邊組成。
一個(gè)節(jié)點(diǎn)可以與眾多個(gè)節(jié)點(diǎn)直接相連，這些節(jié)點(diǎn)被稱為鄰居。
6.3廣度優(yōu)先搜索
廣度優(yōu)先搜索是一種用于圖的查找算法，可幫助回答兩類問題：
第一類問題：從節(jié)點(diǎn)A出發(fā)，有前往B節(jié)點(diǎn)的路徑嗎？
第二類問題：從節(jié)點(diǎn)A出發(fā)，前往節(jié)點(diǎn)B的哪條路徑最短呢？
拿賣水果的例子來(lái)說，如果你的朋友不是經(jīng)銷商的話，就將你的朋友也加入到名單中。這意味著你將在她的朋友、朋友的朋友等中查找。使用這種算法將搜遍你的整個(gè)人際關(guān)系網(wǎng)，知道找到水果經(jīng)銷商。這就是廣度優(yōu)先搜索算法。
6.3.1查找最短路徑
首先，拿上文來(lái)說，你應(yīng)該先在一度關(guān)系中搜索，確定其沒有芒果銷售商后，才在二度關(guān)系中搜索。
有一個(gè)可實(shí)現(xiàn)這種目的的數(shù)據(jù)結(jié)構(gòu)，那就是隊(duì)列。
6.3.2隊(duì)列
隊(duì)列的工作原理和現(xiàn)實(shí)生活中的隊(duì)列完全相同。如果你排在他前面，你將先上車。隊(duì)列類似于棧，你不能隨機(jī)地訪問隊(duì)列的元素。
隊(duì)列只支持兩種操作：入隊(duì)和出隊(duì)
隊(duì)列先進(jìn)先出，而棧后進(jìn)先出！
6.4實(shí)現(xiàn)圖
圖由多個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)都與鄰近節(jié)點(diǎn)相連。
散列表讓你能夠?qū)㈡I映射到值，在這里只需要將節(jié)點(diǎn)映射到其所有鄰居。散列表是無(wú)序的，因此添加鍵值對(duì)的順序無(wú)關(guān)緊要！
關(guān)系單向：有向圖
無(wú)向圖沒有箭頭，直接相連的節(jié)點(diǎn)互為鄰居。
6.5實(shí)現(xiàn)算法
首先，創(chuàng)建一個(gè)隊(duì)列。在Python中，可使用函數(shù)deque來(lái)創(chuàng)建一個(gè)雙端隊(duì)列。
from collections import deque
search_queue=deque()
search_queue+=graph["you"]
別忘了，這里的graph[‘you’]是一個(gè)數(shù)組，其中包含了你的所有鄰居，如[‘a(chǎn)lice’,‘bob’,‘claire’]。這些鄰居都將加入到搜索隊(duì)列里。
while search_queue:
person=search_queue.popleft()
if person_is_seller(person):
print(person + 'is seller')
return True
else:
search_queue+=graph[person]
return False
最后你還需要編寫函數(shù)來(lái)判斷一個(gè)人是不是經(jīng)銷商，如下所示：
def person_is_seller(name):
return name[-1]=='m'
檢測(cè)這個(gè)人的名字是否以m結(jié)尾：如果是，他就是經(jīng)銷商。這種方法有點(diǎn)搞笑，但就這個(gè)實(shí)例而言是可行的。
這個(gè)算法將不斷執(zhí)行，直到滿足以下條件之一：
1.找到一位經(jīng)銷商
2.隊(duì)列為空，這將意味著你的人際關(guān)系網(wǎng)中沒有經(jīng)銷商。
A既是B的朋友，又是C的朋友，因此他會(huì)兩次被加入到隊(duì)列中，這就會(huì)導(dǎo)致后手檢測(cè)的將變成無(wú)用功。
from collections import deque
def search(name):
search_queue =deque()
search_queue+=graph[name]
searched=[]#這個(gè)數(shù)組用于記錄檢查過的人
while search_queue:
person = search_queue.popleft()
if person not in searched:#僅當(dāng)這個(gè)人沒檢查過時(shí)才檢查
if person_is_seller(person):
print(person+'is seller')
return True
else:
search_queue+=graph[person]
searched.append(person)#將這個(gè)人標(biāo)記為檢查過
return False
search("you")
6.5.1運(yùn)行時(shí)間
如果你的整個(gè)人際關(guān)系網(wǎng)中搜索芒果銷售商，就意味著你將沿著每條邊前行，因此運(yùn)行時(shí)間至少O（邊數(shù)）
你還使用了一個(gè)隊(duì)列，其中包含要檢查的每個(gè)人。將一個(gè)人添加到隊(duì)列需要的時(shí)間是固定的，即為O（1），因此對(duì)每個(gè)人都這樣做需要的總時(shí)間為O（人數(shù)）。所以，廣度優(yōu)先搜索的運(yùn)行時(shí)間為O（人數(shù)加邊數(shù)），通常記作O（V+E），其中V為頂點(diǎn)數(shù)，E為邊數(shù)。
6.5.2樹
有一種圖由節(jié)點(diǎn)和邊組成，但沒有往上指的箭頭，這種圖被稱為樹，樹是一種特殊的圖！
6.6小結(jié)
1.廣度優(yōu)先搜索指出是否有從A到B的路徑；
2.如果有，廣度優(yōu)先搜索將找出最短路徑；
3.面臨類似于尋找最短路徑的問題時(shí)，可以嘗試使用圖來(lái)建立模型，再使用廣度優(yōu)先搜索來(lái)解決問題；
4.有向圖的邊為箭頭，箭頭的方向指定了關(guān)系的方向；
5.無(wú)向圖的邊不帶箭頭，其中關(guān)系是雙向的。
6.隊(duì)列是先進(jìn)先出的；
7.棧是后進(jìn)先出的
8.你需要按加入順序檢查搜索列表中的人，否則找到的就不是最短路徑，因此搜索列表必須是隊(duì)列。
9.對(duì)于檢查過的人，務(wù)必不要再去檢查，否則可能導(dǎo)致無(wú)限循環(huán)。
二級(jí)目錄
三級(jí)目錄
最后的福利
??????最后一點(diǎn)小福利帶給大家：如果想快速上手python的小伙伴們，這個(gè)詳細(xì)整理PPT可以迅速幫助大家打牢python基礎(chǔ)，需要的小伙伴們可以下載一下 Python入門基礎(chǔ)教程全套+小白速成+學(xué)不會(huì)來(lái)找我！
還有自制表白神器，需要自?。?/p>
Python表白神器，源碼+解析+各種完美配置+浪漫新穎
好啦，這就是今天要給大家分享的全部?jī)?nèi)容了
如果你喜歡的話，就不要吝惜你的一鍵三連了~
本文摘自 ：https://blog.51cto.com/u
