第一篇部落格——算法基礎：廣度優先搜尋

第一篇部落格——算法基礎：廣度優先搜尋

基礎概念

圖：由邊和節點組成。

隊列：先進先出的資料結構。

散清單：Key-Value的資料結構，通過散列函數進行映射。

算法

廣度優先搜尋：是一種尋找從節點A到節點B的路徑的算法。可以回答兩類問題：

1. 是否存在節點A到節點B的路徑
2. 從節點A到節點B哪條路徑最短

第一類問題

假如你需要尋找你的朋友中是否有芒果經銷商，那麼你的尋找方法是：首先将你的朋友列在名單裡，然後依次檢查名單中的每個人，檢視他是否是芒果經銷商，如果他是，則大功告成；如果他不是，那麼你檢查需要檢查下一個人。如果你的名單裡面都沒有人是芒果經銷商，那麼你需要在朋友的朋友中查找，則在檢查名單中的每個人時，如果他不是，那麼你将他的所有朋友加入名單中。這樣一來，你不僅查找你的朋友，還查找朋友的朋友。這就是廣度優先搜尋算法。

第二類問題

第二類問題是尋找最短路徑問題，你的朋友是一度關系，朋友的朋友是二度關系。在你看來，一度關系勝過二度關系，二度關系勝過三度關系…是以，你應該首先在一度關系中搜尋，如果沒有找到，再在二度關系中搜尋。是以在檢查名單中，需要将一度關系的人放到二度關系的人之前，換言之，檢查名單的人需要考慮順序。隻有按照順序進行查找，才能實作最短路徑。那麼需要用到隊列的資料結構。

實作圖

在圖中，每個節點都與相鄰節點相連。如何表述這種關系，散清單！利用散清單可以将每個節點映射到其所有的鄰居。在python中，可以用字典來實作。

graph = {}

graph[“A”] = [“B”,“C”,“D”]

graph[“B”] = [“E”,“F”,“A”]

graph[“D”] = [“C”,“B”]

…

算法實作

1. 首先建立一個隊列。
2. 将你的朋友（鄰居節點）放到隊列中
3. 依次檢查（隻要隊列不為空）：
   1. if 這個人是芒果經銷商
      1. 大功告成！
   2. else 這個人不是芒果經銷商
      1. 将這個人的朋友加入隊列

4. 最後，如果到達這裡，說明這個隊列裡沒有芒果經銷商。

   注意：為了防止被檢查過的人又被放入隊列，引起死循環，可以将被檢查過的人進行标記。已經檢查過，則不再加入隊列中。

python代碼實作

def search(name):
	search_queue = deque()
	search_queue += graph[name]
	searched = []
	while search_queue:
		person = search_queue.popleft()
		if not person in searched:
			if person_is_seller(person):
				print person + "is a mango seller!"
				return True
			else:
				search_queue += graph[person]
				searched.append(person)
	return False

def person_is_seller(person):
	#省略。。。#
	return True 
	
search("A")

           

算法複雜度

如果你在你的整個人際關系網中搜尋，就意味着你将沿着每一條邊前行，是以運作時間至少為O(邊數)

你還使用了隊列，隊列裡面的人數是你要檢查的人，是以包含了你的整個人際關系網中的每個人，将每個人添加到隊列中的時間是固定的，為O(1).是以總時間為O(人數)。

是以廣度優先搜尋的運作時間為O(人數+邊數)，通常寫作O(V+E),其中V是頂點數，E為邊數。