图的应用中，最重要的一部分就是图的搜索和遍历，图的搜索算法有很多，而BFS是其中一种比较简单的搜索算法。算法核心在于，从初始顶点开始，一层一层遍历搜索顶点，直到所有顶点搜索完毕，如下图所示：
实现这个算法，我们首先定义level字典，保存每个vertex的层级信息，frontier列表用来保存上一层级遍历过的vertex，parent字典用来保存每个vertex的上一个vertex。为此代码的思路如下：
初始化：level，frontier，parent 保存初始顶点 遍历frontier的所有顶点： 定义next列表，保存下一次需要遍历的顶点 遍历所有与frontier中顶点相连的其他顶点： 如果不在level中即没有遍历： 更新level，parent，next frontier = next 层级加一因此我们的代码如下
def bfs_1(graph, start): """ return: 被遍历的顶点次序和level字典 """ level = {start: 0} parent = {start: None} i = 1 frontier = [start] node_visited = [start] while frontier: next = [] for u in frontier: for v in graph.get_connected_nodes(u): if v not in level: level[v] = i parent[v] = u next.append(v) node_visited.append(v) frontier = next i += 1 return node_visited, level根据BFS的核心思想，我们可以对代码进行不同版本的修改，比如利用队列的特性，可以将上述代码简化，结果返回遍历顶点的次序。
def bfs_2(graph, start): explore = [] queue = [start] while queue: node = queue.pop(0) if node not in explore: explore.append(node) for neighbor in graph.get_connected_nodes(node): queue.append(neighbor) return explore如果需要用BFS找到两点之间的最短路径，可以将第一版的代码修改如下：
在for循环中增加是否找到目标顶点的判断条件，如果是则结束遍历，reach_goal标志设为true，最后利用parent字典，反向遍历找到start到goal的路径。
def bfs_path(graph, start, goal): if start == goal: return [start] level = {start: 0} parent = {start: None} i = 1 frontier = [start] node_visited = [start] reach_goal = False while frontier: next = [] for u in frontier: if goal in graph.get_connected_nodes(u): parent[goal] = u reach_goal = True break for v in graph.get_connected_nodes(u): if v not in level: level[v] = i parent[v] = u next.append(v) node_visited.append(v) frontier = next i += 1 if reach_goal: pathlist = [] temp = goal while temp: pathlist.append(temp) temp = parent[temp] pathlist.reverse() return pathlist else: return []第二种方法没有用parent字典，它是保存当前的路径，从而无需对parent字典反向遍历。
def bfs_path_2(graph, start, goal): pathlist = [(start,)] if start == goal: return [start] while len(pathlist) > 0: new_paths = [] while len(pathlist) > 0: curr_path = pathlist.pop(0) curr_node = curr_path[-1] new_nodes = graph.get_connected_nodes(curr_node) # 更新顶点信息 if len(curr_path) > 1: new_nodes = [node for node in new_nodes if node not in curr_path] if goal in new_nodes: goal_path = curr_path + (goal,) return goal_path # 更新路径信息 new_paths += [curr_path + (node,) for node in new_nodes] pathlist.extend(new_paths) else: return []如果需要找到从初始顶点到目标顶点的所有路径，我们只需修改找到目标顶点的判断条件即可，使程序继续执行，这里我们可以利用yield关键字，同时利用集合的差集运算，去掉已经遍历过的顶点。
def bfs_allpaths(graph, start, goal): queue = [(start, [start])] while queue: (vertex, path) = queue.pop(0) for next in set(graph.get_connected_nodes(vertex)) - set(path): if next == goal: yield path + [next] else: queue.append((next, path + [next]))