Hello，大家好我叫是Dream呀，一個有趣的Python部落客，小白一枚，多多關照 ?
入門須知：這片樂園從不缺乏天才，努力才是你的最終入場券！
最後，願我們都能在看不到的地方閃閃發光，一起加油進步
“一萬次悲傷，依然會有Dream，我一直在最溫暖的地方等你”，唱的就是我！哈哈哈~
第六章：廣度優先搜尋
- 6.1圖簡介
- 6.2圖是什麼
- 6.3廣度優先搜尋
- 6.3.1查找最短路徑
- 6.3.2隊列
- 6.4實作圖
- 6.5實作算法
- 6.5.1運作時間
- 6.5.2樹
- 6.6小結
- 二級目錄
- 三級目錄
- 最後的福利
6.1圖簡介
圖算法：廣度優先搜尋！
前往某一地點，需要的最短路徑被稱為是：最短路徑問題
解決最短路徑問題的算法被稱作：廣度優先搜尋
6.2圖是什麼
圖模拟一組連接配接。圖由節點和邊組成。
一個節點可以與衆多個節點直接相連，這些節點被稱為鄰居。
6.3廣度優先搜尋
廣度優先搜尋是一種用于圖的查找算法，可幫助回答兩類問題：
第一類問題：從節點A出發，有前往B節點的路徑嗎？
第二類問題：從節點A出發，前往節點B的哪條路徑最短呢？
拿賣水果的例子來說，如果你的朋友不是經銷商的話，就将你的朋友也加入到名單中。這意味着你将在她的朋友、朋友的朋友等中查找。使用這種算法将搜遍你的整個人際關系網，知道找到水果經銷商。這就是廣度優先搜尋算法。
6.3.1查找最短路徑
首先，拿上文來說，你應該先在一度關系中搜尋，确定其沒有芒果銷售商後，才在二度關系中搜尋。
有一個可實作這種目的的資料結構，那就是隊列。
6.3.2隊列
隊列的工作原理和現實生活中的隊列完全相同。如果你排在他前面，你将先上車。隊列類似于棧，你不能随機地通路隊列的元素。
隊列隻支援兩種操作：入隊和出隊
隊列先進先出，而棧後進先出！
6.4實作圖
圖由多個節點組成，每個節點都與鄰近節點相連。
散清單讓你能夠将鍵映射到值，在這裡隻需要将節點映射到其所有鄰居。散清單是無序的，是以添加鍵值對的順序無關緊要！
關系單向：有向圖
無向圖沒有箭頭，直接相連的節點互為鄰居。
6.5實作算法
首先，建立一個隊列。在Python中，可使用函數deque來建立一個雙端隊列。
from collections import deque
search_queue=deque()
search_queue+=graph["you"] 别忘了，這裡的graph[‘you’]是一個數組，其中包含了你的所有鄰居，如[‘alice’,‘bob’,‘claire’]。這些鄰居都将加入到搜尋隊列裡。
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 最後你還需要編寫函數來判斷一個人是不是經銷商，如下所示：
def person_is_seller(name):
return name[-1]=='m' 檢測這個人的名字是否以m結尾：如果是，他就是經銷商。這種方法有點搞笑，但就這個執行個體而言是可行的。
這個算法将不斷執行，直到滿足以下條件之一：
1.找到一位經銷商
2.隊列為空，這将意味着你的人際關系網中沒有經銷商。
A既是B的朋友，又是C的朋友，是以他會兩次被加入到隊列中，這就會導緻後手檢測的将變成無用功。
from collections import deque
def search(name):
search_queue =deque()
search_queue+=graph[name]
searched=[]#這個數組用于記錄檢查過的人
while search_queue:
person = search_queue.popleft()
if person not in searched:#僅當這個人沒檢查過時才檢查
if person_is_seller(person):
print(person+'is seller')
return True
else:
search_queue+=graph[person]
searched.append(person)#将這個人标記為檢查過
return False
search("you") 6.5.1運作時間
如果你的整個人際關系網中搜尋芒果銷售商，就意味着你将沿着每條邊前行，是以運作時間至少O（邊數）
你還使用了一個隊列，其中包含要檢查的每個人。将一個人添加到隊列需要的時間是固定的，即為O（1），是以對每個人都這樣做需要的總時間為O（人數）。是以，廣度優先搜尋的運作時間為O（人數加邊數），通常記作O（V+E），其中V為頂點數，E為邊數。
6.5.2樹
有一種圖由節點和邊組成，但沒有往上指的箭頭，這種圖被稱為樹，樹是一種特殊的圖！
6.6小結
1.廣度優先搜尋指出是否有從A到B的路徑；
2.如果有，廣度優先搜尋将找出最短路徑；
3.面臨類似于尋找最短路徑的問題時，可以嘗試使用圖來建立模型，再使用廣度優先搜尋來解決問題；
4.有向圖的邊為箭頭，箭頭的方向指定了關系的方向；
5.無向圖的邊不帶箭頭，其中關系是雙向的。
6.隊列是先進先出的；
7.棧是後進先出的
8.你需要按加入順序檢查搜尋清單中的人，否則找到的就不是最短路徑，是以搜尋清單必須是隊列。
9.對于檢查過的人，務必不要再去檢查，否則可能導緻無限循環。
二級目錄
三級目錄
最後的福利
☀️☀️☀️最後一點小福利帶給大家：如果想快速上手python的小夥伴們，這個詳細整理PPT可以迅速幫助大家打牢python基礎，需要的小夥伴們可以下載下傳一下 Python入門基礎教程全套+小白速成+學不會來找我！
還有自制表白神器，需要自取：
Python表白神器，源碼+解析+各種完美配置+浪漫新穎
好啦，這就是今天要給大家分享的全部内容了