代码小工蚁的#《算法图解》#学习笔记-C6广度优先搜索
C6 广度优先搜索breadth-first search
引言
世界上最遥远的距离，不是生与死的距离，不是天各一方，而是，我就站在你的面前，你却不知道我爱你。
——张小娴《荷包里的单人床》
不谈最远，只要最短！
解决“最短路径问题”的算法被称为广度优先搜索
最短路径问题（shorterst-path problem）：找出两样东西之间的最短距离。如跳棋程序走多少步会获胜。
解决最短路径问题的步骤：
1、使用图来建立问题模型；
2、使用广度优先搜索解决问题。
一、什么是图
图模拟一组连接。
图
图由节点（node）和边（edge）组成。
一个节点可能与众多节点直接相连，这些节点称为邻居（neighbors）。
图中Rama是Alex的邻居。
根据边有无指向性，可将图分为：有向图（directed graph）和无向图（undirected graph）
有向图的边带有箭头，箭头的方向指定了关系的方向，其中的关系是单向的。
无向图的边没有箭头，直接相连的节点互为邻居。
有向图与无向图
二、广度优先搜索
广度优先搜索也叫宽度优先搜索，是最简便的图的搜索算法之一。
其别名叫BFS，广度优先搜索会系统地展开并检查图中的所有节点，以找寻结果。
广度优先搜索帮助回答两类问题：
1、从节点A出发，有前往节点B的路径吗？
2、从节点A出发，前往节点B的哪条路径最短？
队列是一种先进先出（First In First Out，FIFO）的数据结构，
栈是一种后进先出（Last In First Out，LIFO）的数据结构。
广度优先搜索的运行时间：通常写作O(V + E)，其中V为顶点（vertice）数（人数），E为边数。
模拟在自己的朋友中搜索芒果销售商
图-朋友关系搜索
广度优先搜索的代码实现：
#coding=utf-8
# 广度优先搜索
from collections import deque
def bf_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(name):
return name[-1] == 'm'
if __name__ == '__main__':
# 创建图
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'] = []
# 广度优先搜索
bf_search("you")
百度百科：宽度优先搜索
