广度优先搜索
广度优先搜索是最简单的图搜索算法之一，也是许多重要的图算法的原型。不少图算法都使用了类似广度优先搜索的思想。以下为《算法导论》中对广度优先搜索的说明。
给定图 G = (V, E) 和一个可以识别的源结点 s ，广度优先搜索队图 G 中的边进行系统性的探索来发现可以从源结点到达的所有结点。该算法能够计算从源结点 s 到每个可到达的结点的距离（最少的边数），同时生成一棵“广度优先搜索树”。该树以源结点 s 为根结点，包含所有可以从 s 到达的结点。对于每个从源结点 s 可以到达的结点 v ，在广度优先搜索树里从结点 s 到结点 v 的简单路径所对应的就是图 G 中从结点 s 到达结点 v 的 “最短路径”，即包含最少边数的路径。
广度优先搜索之所以如此得名，是因为该算法始终是将已发现结点和未发现结点之间的边界，沿其广度方向向外扩展。也就是说，算法需要在发现所有距离源结点 s 为 k 的所有结点之后，才会发现距离源结点 s 为 k + 1 的其他结点。
广度优先搜索具有层级遍历的特性，不少问题依靠于这个层级遍历特性去解决。
广度优先搜索的实现
广度优先搜索的实现依赖于队列结构，依靠队列先进先出的特性，控制结点的访问顺序。
先将源结点 s 入队，当源结点出队时，再将与其相连的结点 v 入队，当结点 v 出队时，又将与结点 v 相连的结点入队，重复进行上述的操作，直到队列为空，这样就会总是先处理与 s 结点相连的结点 v ，再处理与结点 v 的相连结点。以下为参考自《算法导论》的广度优先搜索的伪代码：
def bfs(graph, s): # 初始化图 for vertex in graph.V: # 顶点初始化为白色 vertex.color = WHITE # d 为顶点距离属性 vertex.d = ∞ # p 为顶点前驱属性 vertex.p = None # 源结点初始化，结点第一次被发现标记为灰色，源结点的距离为 0 s.color = GRAY s.d = 0 s.p = None queue = [] queue.append(s) while queue: u = queue.pop(0) for v in graph.Adj[u]: if v.color == WHITE: v.color = GRAY v.d = u.d + 1 v.p = u queue.append(v) # 结点处理完后标记为黑色 u.color = BLACK
对层级的控制
广度优先搜索的一大特点为对图的层级遍历。
但是许多算法书上给出的基础的深度优先搜索写法，在面对有层级需求的问题来说是不足以解决的。 例如 Leetcode 上的题目： ，寻找二叉树中所有层的最右结点。 对于这类题目，在对树的遍历时，需要控制到遍历层次这一信息。这个题目也可以利用深度优先搜索算法去做，但是使用层级遍历的广度优先搜索则是更加合适。在广度优先搜索中，想要控制到层级信息，有两种方法。
一种是利用末尾指针，该指针总是指向每层的最后一饿结点。 另一种方法为逐层处理结点，只有对一层的结点全部处理完成，才开始下一轮处理。每次循环开始处理前，队列中的元素都是同一层的。以下为使用广度优先搜索解答题目 的源码。
# Definition for a binary tree node.class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: def rightSideView(self, root: 'TreeNode') -> 'List[int]': result = list() if root is None: return result queue = list() queue.append(root) last_node = root while queue: node = queue.pop(0) if node.left: queue.append(node.left) if node.right: queue.append(node.right) if last_node == node: result.append(last_node.val) last_node = queue[len(queue) - 1] if queue else None return result
# Definition for a binary tree node.class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: def rightSideView(self, root: 'TreeNode') -> 'List[int]': result = list() if root is None: return result queue = list() queue.append(root) while queue: # 获取每一层的末尾结点 result.append(queue[-1].val) for _ in range(len(queue)): node = queue.pop(0) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result
无权图的单源最短路径
广度优先搜索常用于解决图的单源最短路径问题。当然这只局限于图是无权的情况下。
在无权图中，最短的路径也就是达到结点最少的边数。在一些书本中给出的算法，都会额外用一个距离字段去记录各个结点的距离。而如果只是求源结点到某个目标结点的距离的话，有更为简单的做法，由于广度优先搜索是层级遍历的，所以源结点到目标结点的距离，刚好也是目标结点所在层数。所以在进行广度优先搜索时，记录层数变化，当遇到目标结点时，所在的层数即为单源最短路径。以 作为例题。
将词看作为一个结点，如果词 A 能转变为词 B ，则表示词 A 与词 B 连通，词的变化路径就会形成图，利用广度优先搜索遍历图，在遍历时记录遍历层数，当遇到指定词时，所在层数即为词的变化次数，也就是源词与目标词之间的最短距离。class Solution: def ladderLength(self, beginWord, endWord, wordList): """ :type beginWord: str :type endWord: str :type wordList: List[str] :rtype: int """ def get_next_words(word, wordList): words = [] for i in range(len(word)): left, right = word[:i], word[i + 1:] for char in 'abcdefghijklmnopqrstuvwxyz': if word[i] == char: continue next_word = left + char + right if next_word in wordList: words.append(left + char + right) return words wordList = set(wordList) if endWord not in wordList: return 0 queue = [] queue.append(beginWord) layer = 1 while len(queue) > 0: layer += 1 for _ in range(len(queue)): word = queue.pop(0) for next_word in get_next_words(word, wordList): if next_word == endWord: return layer queue.append(next_word) wordList.remove(next_word) return 0