大纲
广度优先搜索
假设我们有一个朋友圈，我有三个朋友，我的三个朋友分别是小明、小志和小柳，他们分别也有自己的朋友，这个朋友圈的关系我们可以用一个图来表示。
假设我们已经建立好了这个图，问题是，我们能不能很快速的查询到，某个人是不是在这个朋友圈中和我构成朋友关系。
下面我们先基于字典来建立这个图，以“我”为例，将“我”作为键，然后以“我”的三位朋友建立一个列表，作为值，如下建立这个朋友圈。
graph = {}
graph['我'] = ['小明','小志','小柳']
graph['小志'] = ['大黄','小胖']
graph['小明'] = ['亮亮']
graph['小柳'] = ['小军']
graph['大黄'] = []
graph['小胖'] = ['聪聪']
graph['亮亮'] = []
graph['小军'] = []
graph['聪聪'] = []
建立好的朋友圈长下面这个样子，也可以把这个图看作一个树，“我”是根节点，而我的三位直接朋友是分枝节点。
{'我': ['小明', '小志', '小柳'],
'小志': ['大黄', '小胖'],
'小明': ['亮亮'],
'小柳': ['小军'],
'大黄': [],
'小胖': ['聪聪'],
'亮亮': [],
'小军': [],
'聪聪': []}
从思路上可以这样来一步步的解决寻找朋友的问题
如果没有的话，再看朋友的朋友中，能不能找到对应的名字
def search(name1,name2):
search_list = [] #用于保存待检查的名字
search_list.extend(graph[name1])
searched = [] #用于保存检查过的名字
while search_list: #只要待检查名字列表不为空
person = search_list.pop(0) # 取出列表第一个位置的人名，同时将它从列表中删除
if person not in searched: # 保证它在之前没有被检查过
if person == name2: # 如果名字一样就找到了
print('找到了')
return True
else:
search_list.extend(graph[person]) # 如果没找到，将他的朋友也加入到待检查名单列表
searched.append(person) # 同时将他本人加入已检查列表
print('没找到')
return False
search_list是用于存放待检查名字，每次扩的时候，将名字补充入这个列表中。首先就是放入本人的直接朋友。然后遍历这个列表，如果列表中没有找到name2，就将name2对应的朋友也加入到search_list中。具体逻辑可以参考代码中的注释。
小结：广度优先搜索是一种从树结构上查询数据的思路，它先查询离根部最近的所有分枝，然后再由分枝往外扩展搜索。
练习 ：用字典来排序成绩单
对成绩单进行排序的问题，在上一课中我们是使用一个嵌套列表来做的成绩单排序，这个练习中我们尝试用字典来完成这个任务。
course = [['语文',85],['数学',90],['英语',94],['历史',87],['体育',85],['音乐',98]]
course_dict = {k:v for k,v in course}
print(course_dict)
{'语文': 85, '数学': 90, '英语': 94, '历史': 87, '体育': 85, '音乐': 98}
course_sorted = sorted(course_dict.items(),key=lambda x:x[1])
print(course_sorted)
[('语文', 85), ('体育', 85), ('历史', 87), ('数学', 90), ('英语', 94), ('音乐', 98)]
对成绩单进行排序后的结果是一个列表，不再是一个字典了，如果要恢复到一个字典可以再运行一下如下代码
{k:v for k,v in course_sorted}
{'语文': 85, '体育': 85, '历史': 87, '数学': 90, '英语': 94, '音乐': 98}
注意观察，列表中的元素是一个圆括号括起来的一对值，这种数据类型叫做元组（tuple），这种元组使用起来和列表非常相似。
type(course_sorted[0])
下面我们来看看如何用元组来定义课程成绩，并进行排序。可以看到元组是用圆括号来定义的，它和列表的唯一区别是不能修改其中的元素。
course_tuple = (('语文',85),('数学',90),('英语',94),('历史',87),('体育',85),('音乐',98))
sorted(course_tuple,key=lambda x:x[1])
[('语文', 85), ('体育', 85), ('历史', 87), ('数学', 90), ('英语', 94), ('音乐', 98)]