本文共 1318 字，大约阅读时间需要 4 分钟。

一、BFS简介

BFS即breadth-first search,又称为宽度优先搜索，是最简便的图的搜索算法之一，它是使用队列来实现的。

二、BFS解决问题

BFS可以解决两类问题：

三、代码实现

我们以一个人的朋友圈中有没有芒果销售商为例，进行广度优先遍历。

from collections import dequedef persion_is_seller(name):    return name[-1] == 'm'   # 假设一个人如果姓名以m结尾，那他就是芒果销售商graph={   }graph['you'] = ['alice', 'bob', 'claire']graph['bob'] = ['anuj', 'peggy']graph['alice'] = ['peggy']graph['claire'] = ['thom', 'jonny']graph['anuj'] = []graph['jonny'] = []graph['peggy'] = []graph['thom'] = []def BFS(name):    search_queue = deque()    search_queue += graph[name]    searched = []    while search_queue:        # 注：popleft是弹出第一个元素，是在队列中使用的，括号里不可用带参数        # pop是弹出最后一个元素，是用于栈的出栈的，括号里可以带参数        person = search_queue.popleft()        if person not in searched:            if persion_is_seller(person):                print(person + ' is a mango seller')                return True            else:                search_queue += graph[person]                searched.append(person) # 已经遍历过的要做标记，以防止出现无线循环的情况    return FalseBFS('you')