每日一算:广度优先算法 广度优先概念

图算法中最基础的一种，如图中从双子峰到金门大桥该如何走？

广度优先搜索就是以双子峰为起点，先遍历最近的两个点，看是否有双子峰，如果没有则遍历这两个点的各自下个点，继续判断。以此类推，从近到远遍历周边的点。在技术上需要使用队列，因为他是先进先出，有序的判断从近到远的点。

在《算法图解》中举了这样一个例子，找到周边名字中有'm'的人，先找自己的朋友，再找朋友的朋友。

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 person_is_seller(name):
	return name[-1] == 'm'

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 a mango seller")
			else:
				search_queue += graph[person]         ######## 将下一个层级的点加进队列
				searched.append(person)
	return False

search("you")

和我们常见的从A点到B点的最短距离判断不同，这里没有两个点之间的距离加权，所以这样的算法还是比较简单的，下个算法就是学习图算法中涉及加权的迪克斯特拉算法。