# 28 广度优先搜索算法

## 大纲

* 广度优先搜索
* 练习：用字典排序成绩单

## 广度优先搜索

假设我们有一个朋友圈，我有三个朋友，我的三个朋友分别是小明、小志和小柳，他们分别也有自己的朋友，这个朋友圈的关系我们可以用一个图来表示。

假设我们已经建立好了这个图，问题是，我们能不能很快速的查询到，某个人是不是在这个朋友圈中和我构成朋友关系。

下面我们先基于字典来建立这个图，以“我”为例，将“我”作为键，然后以“我”的三位朋友建立一个列表，作为值，如下建立这个朋友圈。

```python
graph = {}
graph['我'] = ['小明','小志','小柳']
graph['小志'] = ['大黄','小胖']
graph['小明'] = ['亮亮']
graph['小柳'] = ['小军']
graph['大黄'] = []
graph['小胖'] = ['聪聪']
graph['亮亮'] = []
graph['小军'] = []
graph['聪聪'] = []
```

建立好的朋友圈长下面这个样子，也可以把这个图看作一个树，“我”是根节点，而我的三位直接朋友是分枝节点。

```python
graph
```

```
{'我': ['小明', '小志', '小柳'],
 '小志': ['大黄', '小胖'],
 '小明': ['亮亮'],
 '小柳': ['小军'],
 '大黄': [],
 '小胖': ['聪聪'],
 '亮亮': [],
 '小军': [],
 '聪聪': []}
```

从思路上可以这样来一步步的解决寻找朋友的问题

* 首先看我的直接朋友中有没有找到对应的名字
* 如果没有的话，再看朋友的朋友中，能不能找到对应的名字
* 这样一层层的往外扩，这种思路就叫作广度优先搜索

```python
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中。具体逻辑可以参考代码中的注释。

```python
search('我','小军')
```

```
找到了

True
```

小结：广度优先搜索是一种从树结构上查询数据的思路，它先查询离根部最近的所有分枝，然后再由分枝往外扩展搜索。

## 练习 ：用字典来排序成绩单

对成绩单进行排序的问题，在上一课中我们是使用一个嵌套列表来做的成绩单排序，这个练习中我们尝试用字典来完成这个任务。

```python
course = [['语文',85],['数学',90],['英语',94],['历史',87],['体育',85],['音乐',98]]
```

```python
course_dict = {k:v for k,v in course}
print(course_dict)
```

```
{'语文': 85, '数学': 90, '英语': 94, '历史': 87, '体育': 85, '音乐': 98}
```

```python
course_sorted = sorted(course_dict.items(),key=lambda x:x[1])
print(course_sorted)
```

```
[('语文', 85), ('体育', 85), ('历史', 87), ('数学', 90), ('英语', 94), ('音乐', 98)]
```

对成绩单进行排序后的结果是一个列表，不再是一个字典了，如果要恢复到一个字典可以再运行一下如下代码

```python
{k:v for k,v in course_sorted}
```

```
{'语文': 85, '体育': 85, '历史': 87, '数学': 90, '英语': 94, '音乐': 98}
```

注意观察，列表中的元素是一个圆括号括起来的一对值，这种数据类型叫做元组（tuple），这种元组使用起来和列表非常相似。

```python
type(course_sorted[0])
```

```
tuple
```

下面我们来看看如何用元组来定义课程成绩，并进行排序。可以看到元组是用圆括号来定义的，它和列表的唯一区别是不能修改其中的元素。

```python
course_tuple = (('语文',85),('数学',90),('英语',94),('历史',87),('体育',85),('音乐',98))
```

```python
sorted(course_tuple,key=lambda x:x[1])
```

```
[('语文', 85), ('体育', 85), ('历史', 87), ('数学', 90), ('英语', 94), ('音乐', 98)]
```