广度优先搜索之双向bfs（实操篇） |
您所在的位置：网站首页 › 双向逻辑查找 › 广度优先搜索之双向bfs（实操篇） |
广度优先搜索之双向bfs（实操篇）
|
文章目录
前言朴素bfs的求解思路双向bfs的求解思路单词接龙题目描述朴素bfs双向bfs小结
打开转盘锁题目描述双向bfs
滑动谜题题目描述双向bfs
公交路线题目描述双向bfs
结语
前言
对于bfs（广度优先搜索）相信大家都有所耳闻，在很多场合下都会用到它，比如最经典的树的层次遍历以及图的广度搜索。但是对于双向bfs也许就大家就会感到一些陌生了，双向bfs，顾名思义就是从两边同时进行bfs遍历，但是为何会需要使用双向bfs呢？（以下的图片以及描述来自力扣三叶姐） 使用朴素 bfs 进行求解时，队列中最多会存在“两层”的搜索节点。 因此搜索空间的上界取决于 目标节点所在的搜索层次的深度所对应的宽度。 在朴素的 BFS 实现中，空间的瓶颈主要取决于搜索空间中的最大宽度。 下图展示了朴素 BFS 可能面临的搜索空间爆炸问题：
按照刚才所描述朴素bfs的思路，直接上代码： function ladderLength(beginWord: string, endWord: string, wordList: string[]): number { if (beginWord === endWord) { return 0; } if (!wordList.includes(endWord)) { return 0; } const isCheck = (word: string, str: string) => { if (word.length !== str.length) { return false; } let count = 0; for (let i = 0; i < word.length; i++) { if (word[i] !== str[i]) { count++; } if (count >= 2) { return false; } } return count === 1; } const get = (str: string) => { const res = []; wordList.forEach(word => { if (isCheck(word, str)) { res.push(word); } }) return res; } // 核心队列 const queen = []; // 用于保存已经遍历过的节点 const seen = new Set(); // 用于记录当前遍历的层数 let step = 0; queen.push(beginWord); seen.add(beginWord); // 外层循环是遍历的其中一个终止条件 while (queen.length) { step++; // 内层循环只遍历当前层数的所有节点 const size = queen.length; for (let i = 0; i < size; i++) { // 节点出队 const word = queen.shift(); // 找到当前节点的所有满足调条件的子节点 for (let nextWord of get(word)) { if (!seen.has(nextWord)) { // 找到目标数据，直接返回 if (nextWord === endWord) { return step + 1; } // 否则入队，继续遍历 queen.push(nextWord); seen.add(nextWord); } } } } return 0; };bfs的注释应该很详细，至于get方法相关的代码没有注释是因为它会随着题目的变化而变化，因为它的逻辑与bfs没有关系。 双向bfs按照刚才所描述双向bfs的思路，直接上代码： function ladderLength(beginWord: string, endWord: string, wordList: string[]): number { if (beginWord === endWord) { return 0; } if (!wordList.includes(endWord)) { return 0; } const isCheck = (word: string, str: string) => { if (word.length !== str.length) { return false; } let count = 0; for (let i = 0; i < word.length; i++) { if (word[i] !== str[i]) { count++; } if (count >= 2) { return false; } } return count === 1; } const get = (str: string) => { const res = []; wordList.forEach(word => { if (isCheck(word, str)) { res.push(word); } }) return res; } // 三个参数，分别标书当前被遍历的队列，当前队列的所属map以及另外一个队列的所属map const update = (queen: string[], cur: Map, other: Map) => { const size = queen.length; // 遍历队列当前层次的所有节点 for (let i = 0; i < size; i++) { // 出队 const word = queen.shift(); // 取出当前节点的遍历层数 const step = cur.get(word); // 找到当前节点的所有满足调条件的子节点 for (let nextWord of get(word)) { // 当前队列的map中存在了，说明已经遍历过，无需再重复遍历，直接跳过 if (cur.has(nextWord)) { continue; } // 在另外一个队列的map中发现了当前队列即将要遍历的节点，说明头尾以及对接上了，即找到了最短路径 if (other.has(nextWord)) { return step + 1 + other.get(nextWord); } else { // 否则入队，继续遍历 cur.set(nextWord, step + 1); queen.push(nextWord); } } } return -1; } // 核心的两个队列，代表两个方向的搜索 const queen1 = []; const queen2 = []; queen1.push(beginWord); queen2.push(endWord); // 两个map，k表示已经遍历的节点，v表示当前遍历处于的层数。 const map1 = new Map(); const map2 = new Map(); map1.set(beginWord, 0); map2.set(endWord, 0); // 只要有一个队列为空，则退出循环，遍历结束 while (queen1.length && queen2.length) { let t = -1; // 选择长度更小的队列进行遍历 if (queen1.length { return x === '0' ? '9' : (parseInt(x) - 1) + ''; } const numSucc = (x: string) => { return x === '9' ? '0' : (parseInt(x) + 1) + ''; } // 枚举 status 通过一次旋转得到的数字 const get = (status: string) => { const ret = []; const array = Array.from(status); for (let i = 0; i < 4; ++i) { const num = array[i]; array[i] = numPrev(num); ret.push(array.join('')); array[i] = numSucc(num); ret.push(array.join('')); array[i] = num; } return ret; } const update = (queen: string[], cur: Map, other: Map) => { const size = queen.length; for (let i = 0; i < size; i++) { const status = queen.shift(); const step = cur.get(status); for (const nextStatus of get(status)) { if (dead.has(nextStatus)) { continue; } if (cur.has(nextStatus)) { continue; } if (other.has(nextStatus)) { return step + 1 + other.get(nextStatus); } else { queen.push(nextStatus); cur.set(nextStatus, step + 1); } } } return -1; } const queen1 = []; const queen2 = []; queen1.push('0000'); queen2.push(target); const map1 = new Map(); const map2 = new Map(); map1.set('0000', 0); map2.set(target, 0); while (queen1.length && queen2.length) { let t = -1; if (queen1.length { const res = []; // 将str转换成二维数组 const arr = []; for (let i = 0; i < 2; i++) { const tmp = []; for (let j = 0; j < 3; j++) { tmp.push(Number(str[i * 3 + j])); } arr.push(tmp); } // 生成可以转换的新格式 2*3网格 7种方案 （只能以0为开始进行交换） for (let i = 0; i < 2; i++) { for (let j = 1; j < 3; j++) { if (arr[i][j - 1] === 0 || arr[i][j] === 0) { [arr[i][j - 1], arr[i][j]] = [arr[i][j], arr[i][j - 1]]; res.push(arr.flat().join('')); [arr[i][j], arr[i][j - 1]] = [arr[i][j - 1], arr[i][j]]; } } } for (let i = 1; i < 2; i++) { for (let j = 0; j < 3; j++) { if (arr[i - 1][j] === 0 || arr[i][j] === 0) { [arr[i - 1][j], arr[i][j]] = [arr[i][j], arr[i - 1][j]]; res.push(arr.flat().join('')); [arr[i][j], arr[i - 1][j]] = [arr[i - 1][j], arr[i][j]]; } } } return res; } const update = (queue: string[], cur: Map, other: Map) => { const size = queue.length; for (let i = 0; i < size; i++) { const str = queue.shift(); const step = cur.get(str); for (let nextStr of get(str)) { if (cur.has(nextStr)) { continue; } if (other.has(nextStr)) { return step + 1 + other.get(nextStr); } else { cur.set(nextStr, step + 1); queue.push(nextStr); } } } return -1; } while (queue1.length && queue2.length) { let t = -1; if (queue1.length { const res = []; for (let i = 0; i < routes.length; i++) { if (!car.has(i) && routes[i].includes(point)) { car.add(i); for (let j = 0; j < routes[i].length; j++) { if (routes[i][j] !== point && !res.includes(routes[i][j])) { res.push(routes[i][j]); } } } } return res; } const update = (queue: number[], cur: Map, other: Map, car: Set) => { while (queue.length) { const size = queue.length; for (let i = 0; i < size; i++) { const point = queue.shift(); const step = cur.get(point); for (let nextPoint of get(car, point)) { if (cur.has(nextPoint)) { continue; } if (other.has(nextPoint)) { return step + 1 + other.get(nextPoint); } else { cur.set(nextPoint, step + 1); queue.push(nextPoint); } } } } return -1; } while (queue1.length && queue2.length) { let t = -1; if (queue1.length |
此时，双向bfs就能很好的解决这个问题： 同时从两个方向开始搜索，一旦搜索到相同的值，意味着找到了一条联通起点和终点的最短路径。 对于有解、有一定数据范围同时层级节点数量以倍数或者指数级别增长的情况，双向bfs的搜索空间通常只有朴素 bfs的空间消耗的几百分之一，甚至几千分之一。正是由于其需要搜索的数量大幅减少，所以双向bfs所消耗的时间往往也比朴素bfs所消耗的时间少得多。 
接下来我分别详细讲述朴素bfs的实现思路以及双向bfs的求解思路，然后给出四道力扣的题目作为实操案例。
这里题目描述不是重点，所以我直接用截图，想看原题的可以直接点链接跳转过去。 单词接龙【本文地址】
今日新闻 |
推荐新闻 |