搞定算法与数据结构(03):BFS(广度优先查找)最短路径案例模板
查看完整目录 –>《搞定算法与数据结构》
给定问题
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列:
- 序列中第一个单词是 beginWord 。
- 序列中最后一个单词是 endWord 。
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ,找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0。
示例1
输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出:5
解释:一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
示例2
输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出:0
解释:endWord "cog" 不在字典中,所以无法进行转换。
解题思路
最短路径的问题,都可以使用广度优先的思路来解决。
第一步:数据预处理
给定的原始数据只有一个数组
wordList = ["hot","dot","dog","lot","log"]
要想使用广度优先的解法,第一步必须把已知数据,整理具体有如下图依赖关系的数据结构
假设用 map 来存储这一依赖关系,就需要用遍历来找到找有的可能性。
wordList = ["hot","dot","dog","lot","log","cog"]
def construct_dict():
map = {}
for word in wordList:
for index in range(len(word)):
s = word[:index] + "_" + word[index+1:]
map[s] = map.get(s, []) + [word]
return map
construct_dict()
将 map 打印出来,虽然存储内容与上面图中的并不完全相同,但可以达到的目的是一样的。
{
'_og': ['dog', 'log', 'cog'],
'_ot': ['hot', 'dot', 'lot'],
'c_g': ['cog'],
'co_': ['cog'],
'd_g': ['dog'],
'd_t': ['dot'],
'do_': ['dot', 'dog'],
'h_t': ['hot'],
'ho_': ['hot'],
'l_g': ['log'],
'l_t': ['lot'],
'lo_': ['lot', 'log']
}
第一轮
有了 map ,后面就可以从 beginWord = ‘hit’开始,遍历改变一个字符三种可能性:_it
,h_t
,hi_
再分别从 map 中找到所有符合的字符串,放入到一个队列 Q 中,若有找到,则转换次数加 1,并把该 beginWord 放入已访问的集合中,若无找到,直接返回 0。
第二轮
从上面的 Q 中,取出上一轮找到的字符串,对每个字符串 s ,同样遍历三种可能性 pattern,每一个可能性pattern,都去 map 中查找符合的字符串,若有的字符串已经访问过了,直接跳过,若还没有访问过,则再次放入 Q 中,并把 s 放入已访问的集合中。
往复轮回
重复以上步骤,直到找到某一个字符串刚好是目的的字符串,结束查找。
代码如下
def bfs(begin, target, d):
queue, visited = [(begin, 1)], set()
while len(queue) > 0:
word, steps = queue.pop(0)
if word not in visited:
visited.add(word)
if word == target:
return steps
for i in xrange(len(word)):
s = word[:i] + "_" + word[i+1:]
for j in d.get(s, []):
# 如果j在visited中,说明j已经被访问过了,不需要再次进行访问。
if j not in visited:
queue.append((j, steps+1))
return 0
经验总结
使用广度优先算法解题,要准备:
- 已访问元素的集合,以便判断某些元素已经访问过了,重复访问永远不可能是最短路径
- 待访问元素的集合,以便一轮访问完成后,知道下一轮要访问哪些元素
- 能够直接或间接表示图结构的数据结构,如上面的 map