简介
广度优先搜索算法（Breathed First Search）是一种搜索算法。原理就是从树的根节点开始去遍历所有节点，从而找出最短路径。
使用范围
- 可以用来走迷宫，在游戏领域中可以用来做自动寻路功能
- 可以用来编写跳棋AI，计算多少步能获胜
- 也可以用来根据自己的人际关系网络查找到关系最近的医生
图
图由节点和边组成。一个节点可能与众多节点直接相连
图用于模拟不同的东西是如何相连的。
类似这样模拟了欠债关系的就是图
在遇到能用广度优先搜索算法解决问题时，我们可以先借助图来建立问题模型，然后再通过算法去解决问题。
图只是用来模拟问题模型，并不是最终答案
树形结构也是一种图，与其他图不同的是它不会往后指。
也就是说遇到问题后，我们可以通过图把问题的关键点放在节点上。用散列表把这些点按照图的结构存储起来，然后再执行搜索找到最佳路径。
可能看文字描述有点太抽象，刷几道题来找找感觉！
实践
题1 从好友名单中找出关系最近医生
解题思路：
1. 创建一个队列，用于存储查找名单
2. 从队列中弹出一个人
3. 检查这个人是不是医生
4. 如果是— 查找成功
5. 如果不是，将此人的邻居加入队列
6. 回到第二步
from collections import deque
# 以图为模型 建立散列表数据
graph = {}
graph["you"] = ["alice", "bob", "clarie"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["clarie"] = ["thom", "jonny", "doctor"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
graph["doctor"] = []
def search(name):
# 因为搜索
search_queue = deque()
search_queue += graph['you']
searched = []
while search_queue:
person = search_queue.popleft()
if person not in searched:
if person_is_doctor(person):
print(person + " is a doctor!")
break
else:
search_queue += graph[person]
searched.append(person)
def person_is_doctor(name):
return name[-1] == 'r'
search("you")
题2 来源于leetcode
给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。
比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。
现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。
示例 1:
输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出: 11
解释:
员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。
注意:
一个员工最多有一个直系领导，但是可以有多个直系下属
员工数量不超过2000。
解题思路
- 和先前一样，为了确保顺序把所有节点放入队列中
- 考虑到数据方便操作，把员工的数据存入到散列表中。以id为键
- 遍历到对应员工数据后增加重要度值
- 按队列顺序遍历subordinates值，把其下属员工继续放入到队列中。继续搜索
"""
# Employee info
class Employee:
def __init__(self, id: int, importance: int, subordinates: List[int]):
# It's the unique id of each node.
# unique id of this employee
self.id = id
# the importance value of this employee
self.importance = importance
# the id of direct subordinates
self.subordinates = subordinates
"""
from collections import deque
class Solution:
def getImportance(self, employees: List['Employee'], id: int) -> int:
score = 0
hash_map = dict()
for emp in employees:
hash_map[emp.id] = emp
search_queue = deque()
search_queue.append(id)
while search_queue:
search_id = search_queue.popleft()
score += hash_map[search_id].importance
for item in hash_map[search_id].subordinates:
search_queue.append(item)
return score