搞定算法与数据结构(03):BFS(广度优先查找)最短路径案例模板

作者: 王炳明 分类: 算法与数据结构 发布时间: 2021-10-02 23:22 热度:1,926

查看完整目录 –>《搞定算法与数据结构


给定问题

来自:Letcode (127) – 课程表 2

字典 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"]

要想使用广度优先的解法,第一步必须把已知数据,整理具体有如下图依赖关系的数据结构

搞定算法与数据结构(03):BFS(广度优先查找)最短路径案例模板

假设用 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’开始,遍历改变一个字符三种可能性:_ith_thi_

再分别从 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

文章有帮助,请作者喝杯咖啡?

发表评论