[AIGC] 宽度优先搜索(BFS) 讲解以及在 LeetCode 题中的应用

宽度优先搜索（Breadth-First Search，简称 BFS）是一种用于图或树结构的遍历算法。它以广度方向进行搜索，首先访问根节点，然后访问所有相邻的节点，然后再通过它们的邻居一直进行下去，直到所有的节点都被访问过。

BFS 的工作过程

BFS 从图的某一节点（称为“源”节点）开始，访问可能的所有顶点，并采取先来先服务的原则。 按照这个算法的一般操作步骤，首先创建一个队列，然后将源节点入队。然后，在图遍历过程中，当队列不为空时，从队列的头部出队一个节点，并将它的所有未访问过的邻居入队。一旦节点被标记为 “已访问”，则表示该节点已经完成了遍历。

BFS 在 LeetCode 中的应用

我们来看一看在 LeetCode 上的题编号 127，题目《单词接龙》。

题目大致为：给定两个单词（beginWord和endWord）和一个字典 wordList ，找出所有从 beginWord 到 endWord 的最短转换序列，转换需遵循如下规则：
每次转换只能改变一个字母，转换过程中的中间单词必须是字典中的单词。

这是一个标准的 BFS 问题，适合应用 BFS 来寻找字典中单词的最短转化路径。

这是该问题的 Python 代码实现：

from collections import defaultdict, deque
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList: return 0
        l = len(beginWord)
        ws = defaultdict(list)
        for word in wordList:
            for i in range(l):
                ws[word[:i]+'*'+word[i+1:]].append(word)

        déf bfs(q: deque, v: dict) -> int:
            s, d = q.popleft()
            for i in range(l):
                nw = s[:i] + '*' + s[i+1:]
                for word in ws[nw]:
                    if word == endWord: return d+1
                    if word not in v:
                        v[word] = True
                        q.append((word, d+1))
            return 0
        qq, qe,v1, v2, flg  = deque(), deque(), {}, {}, 0
        qq.append((beginWord, 1))
        v1[beginWord] = True
        return bfs(qq, v1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

在以上代码中，定义了双向宽度优先搜索 (bidirectional breadth-first search) 的框架，遍历的过程后都加入遍历的节点到队列，这样直到找到终止点位置或者结束遍历。对于队列中每个节点，都找他的下一个位置，将其加入到队列中，这样就实现了 BFS 遍历。此问题的求解就是找出从起始点到终止点的最短路径，也就是 BFS 中第一次找到的路径就是最短的路径。