- 《算法图解》学习笔记
图是什么？
图模拟一组连接，用于模拟不同的东西是如何相连的。例如：
图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。
有向图（directed graph）的关系是单向的，无向图（undirected graph）没有箭头，直接相连的节点互为邻居。例如，下面两个图是等价的。
广度优先搜索
广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。
- 第一类问题：从节点A出发，有前往节点B的路径吗？
- 第二类问题：从节点A出发，前往节点B的哪条路径最短？
我们来看下面的一个图
寻找芒果销售商
现在假设你要寻找一个芒果经销商，你寻找的途径一般是询问自己的朋友，如果朋友中没有芒果经销商，就可以拜托朋友去询问他的朋友，在图中我们可以看到，你自己的朋友是一度关系，也就是比较亲密，如果自己的朋友就是经销商，何必再去二度关系——朋友的朋友那里寻找呢？这就是广度优先搜索，在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。
你按顺序依次检查名单中的每个人，看看他是否是芒果销售商。这将先在一度关系中查找，再在二度关系中查找，因此找到的是关系最近的芒果销售商。广度优先搜索不仅查找从A到B的路径，而且找到的是最短的路径。
代码实现
图由多个节点组成。每个节点都与邻近节点相连，如果表示类似于“你→Bob”这样的关系呢？我们可以使用散列表，散列表让你能够将键映射到值。在这里，你要将节点映射到其所有邻居。
你与你的邻居，“你”为一个键，“邻居”为值
表示这种映射关系的Python代码如下。
graph = {} # 建立一个空字典
graph["you"] = ["alice", "bob", "claire"] # 你对应你的邻居们
那么全部的图，代码可以这样表示了（节点为键或值，边则对应着键值的关系）
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"] = []
接下来我们使用队列这个数据结构，按序查找，首先询问一度关系的朋友，如果该朋友不是经销商，那么把该朋友的朋友再加入到队列中来，依次类推，完成问询。如果队列空了，就表示你的朋友关系网中没有芒果经销商。
如果遇到关系是双向的，或者一个朋友即使你的朋友也是你朋友的朋友，就会产生一些问题，会将同一个人查询两次或多次，导致无限循环。于是，我们需要创建一个列表，存储已经询问过的人，当他再次在队列中出现时，不必询问。
最终示例代码如下
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:
person = search_queue.popleft() # 出队，准备查询队列中第一个人
if person not in searched:
if person_is_seler(person): # 判断是否为经销商
print(person+"is a mango seller")
return True
else:
search_queue += graph[person] # 该朋友不是经销商，遂将该朋友的朋友加入队列
searched.append(person) # 将该朋友记录到已询问名单
return False
search("you")
运行时间
如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是从一个人到另一个人的箭头或连接），因此运行时间至少为O（边数）。
你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为O(1)，因此对每个人都这样做需要的总时间为O(人数)。所以，广度优先搜索的运行时间为O(人数+边数)，这通常写作O(V+E)，其中V为顶点（vertice）数，E为边数。
