廣度優(yōu)先搜索
(breadth-first search,BFS)是一種圖算法柒莉，能找出兩樣?xùn)|西之間的最短距離纲熏。
最短路徑問(wèn)題，比如乘車去某個(gè)地點(diǎn)棚辽，中間需要換乘技竟，路線有很多種，但總存在一條換乘最少的屈藐，最短路徑榔组。
基本概念
圖
圖由節(jié)點(diǎn)(node)、邊(edge)組成联逻。
在圖中相互連接的節(jié)點(diǎn)被稱為鄰居搓扯。
廣度優(yōu)先搜索
這種算法用來(lái)解決2類問(wèn)題：
- 是否存在路徑
- 哪條路徑最短
隊(duì)列
在廣度優(yōu)先搜索中，搜索范圍從起點(diǎn)向外延伸包归，但是對(duì)于數(shù)據(jù)需要按添加順序查找锨推。于是需要用到隊(duì)列(queue)這一數(shù)據(jù)結(jié)構(gòu)
隊(duì)列(First in First Out,FIFO),先進(jìn)先出；棧(Last In First Out,LIFO).
有向圖(directed graph),有箭頭指向；對(duì)應(yīng)無(wú)向圖(undirected graph)
算法原理
1.創(chuàng)建一個(gè)隊(duì)列换可，用于存儲(chǔ)數(shù)據(jù)
2.從隊(duì)列中彈出一個(gè)數(shù)據(jù)椎椰，檢查是否符合搜索條件
3.如果不符合條件則將該數(shù)據(jù)的所有鄰居都加入隊(duì)列，然后重復(fù)2
4.當(dāng)隊(duì)列為空沾鳄，說(shuō)明找不到符合條件的結(jié)果
python代碼實(shí)現(xiàn)---找芒果商例子
from collections import deque
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"] = []
def search(name):
search_queue = deque()
search_queue +=graph[name]
searched = []
#條件列表不為空
while search_queue:
#從隊(duì)列取第一個(gè)值
person = search_queue.popleft()
if not person in searched:
if person_is_seller(person):
print(person+' is a mango seller!')
return True
else:
#將該元素的鄰居加入隊(duì)列
search_queue += graph[person]
searched.append(person)
return False
def person_is_seller(name):
#假設(shè)的芒果商選擇依據(jù)慨飘，名字末尾以m結(jié)尾
return name[-1] =='m'
該算法運(yùn)行時(shí)間是由邊數(shù)和人數(shù)決定的。O(V+E)译荞，vertice and egde
拓?fù)渑判?/h1>
A依賴于B瓤的，在列表中A必須在B之后，是一個(gè)有序列表吞歼。
樹(shù)圖
需要補(bǔ)充
參考
《算法圖解》
