算法| DFSBFS套路

本文主要是介绍算法| DFSBFS套路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DFS&BFS 套路

dfs

--- 初始化checklist答案
--- dfs入口
--- dfs函数答案更新终止条件限制条件递归dfs函数
--- 返回答案

// 给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
var canVisitAllRooms2 = function (rooms) {let len = rooms.length;const checkList = Array(len).fill(0);//   初始化 第一个房间可以进入checkList[0] = 1;function dfs(room) {for (let key of room) {if (checkList[key] === 0) {checkList[key] = 1;// 把这个房间的值进入dfs遍历dfs(rooms[key]);}}}dfs(rooms[0]);let ans = checkList.every((item) => item === 1);return ans;
};
console.log(canVisitAllRooms2([[1, 3], [3, 0, 1], [2], [0]])); // false

bfs

1. 通用 bfs

---- 初始化checkListqueue
---- 首元素加入队列
---- 循环队列while(queue.length)取出队头shift限制条件往队列里加入新的元素更新checkList
---- 返回答案

2. 多源 bfs

---- 初始化checkListqueuelevel
---- 首批（多个）元素加入队列
---- 循环队列while(queue.length)for循环拿出第一批数据取出队头shift限制条件往队列里加入新的元素更新checkList
---- 返回答案

/*** @param {number[][]} grid* @return {number}*/
var orangesRotting = function (grid) {let level = 0;let freshNum = 0;let x = grid.length;let y = grid[0].length;let queue = [];let dir = [[1, 0],[-1, 0],[0, 1],[0, -1],];let checkList = Array(x).fill(0).map(() => Array(y).fill(0));// 统计一开始就腐烂的橘子和新鲜橘子的数目for (let i = 0; i < x; i++) {for (let j = 0; j < y; j++) {if (grid[i][j] === 2) {queue.push([i, j]);checkList[i][j] = 1;} else if (grid[i][j] === 1) {freshNum += 1;}}}//   没有新鲜橘子if (freshNum === 0) return 0;while (queue.length > 0) {const len = queue.length;// 每经过一次队列，leve+1level += 1;// 把队列中的全部拿出来for (let k = 0; k < len; k++) {// 拿到腐烂橘子的信息const [i, j] = queue.shift();// 四个方向for (let d = 0; d < dir.length; d++) {let nextI = i + dir[d][0];let nextJ = j + dir[d][1];// 边界 + 未检查 + 新鲜橘子 ，加入队列//  js中不能用 <= x < 这种 判断条件， 判断不准if (nextI >= 0 &&nextI < x &&nextJ >= 0 &&nextJ < y &&checkList[nextI][nextJ] === 0 &&grid[nextI][nextJ] === 1) {queue.push([nextI, nextJ]);checkList[nextI][nextJ] = 1;//   新鲜橘子-1freshNum -= 1;}}}}if (freshNum > 0) return -1;return level - 1;
};
console.log(orangesRotting([[2, 1, 1],[1, 1, 0],[0, 1, 1],])
);

3. 拓扑排序 bfs

---- 初始化入度表邻接表队列
---- 根据入度表 初始化队列元素
---- 循环队列拿出元素根据邻接表获取对应值入度表--入度表为0加入队列计算答案
---- 返回答案

/*** 返回依赖排序* @param {*} tasks  任务*/
//==========================重点====================
// 1. bfs方式 借助队列， 存入队列，读取队列
// 2. 看到存在依赖关系， 立马想到拓扑排序， 入度出度
// 3.  "B->A"  A 依赖B
const getTaskOrder = (tasks) => {const len = tasks.length;const grid = tasks.map((item) => item.split("->"));console.log("grid", grid);let taskList = [];const intDegree = {};let ans = "";const map = {};for (let i = 0; i < len; i++) {let cur = grid[i][1];let next = grid[i][0];intDegree[next] === undefined? (intDegree[next] = 1): (intDegree[next] += 1);intDegree[cur] === undefined ? (intDegree[cur] = 0) : "";map[cur] === undefined ? (map[cur] = [next]) : map[cur].push(next);}console.log(intDegree);console.log(map);let queue = [];Object.keys(intDegree).forEach((key) => {if (intDegree[key] === 0) {queue.push(key);taskList.push(key);}});ans = taskList.sort().join(" ");taskList = [];while (queue.length) {let cur = queue.shift();let next = map[cur];if (next && next.length) {for (let i = 0; i < next.length; i++) {let val = next[i];intDegree[val]--;if (intDegree[val] === 0) {queue.push(val);taskList.push(val);}}}}return ans + " " + taskList.sort().join(" ");
};
console.log(getTaskOrder(["B->A", "C->A", "D->B", "D->C", "D->E"])); // A E B C D

4. 启发 bfs

---- 不用队列了， 借用数组
---- 每走一步都选取最优值
---- while循环满足条件退出更新答案

// 题目描述
// 评估一个网络的信号质量，其中一个做法是将网络划分为栅格，然后对每个栅格的信号质量计算，路测的时候，希望选择一条信号最好的路线（彼此相连的栅格集合）进行演示，现给出R行C列的整数数组COV，每个单元格的数值S即为该栅格的信号质量（已归一化，无单位，值越大信号越好）
// 要求从[0,0]到[R-1,C-1]设计一条最优路测路线。返回该路线得分。规则:
// 1. 路测路线可以上下左右四个方向，不能对角
// 2. 路线的评分是以路线上信号最差的栅格为准的，例如路径8->4->5->9的值为 4，该线路评分为4。线路最优表示该条线路的评分最高。// 输入描述
// 第1行表示栅格的行数R
// 第2行表示栅格的列数C
// 第3行开始，每一行表示栅格地图一行的信号值，如5 4 5// 输出描述
// 最优路线的得分// 补充说明
// 1 <= R,C <= 20
// 0 <= S <= 65535// 示例
// 输入
// 3
// 3
// 5 4 5
// 1 2 6
// 7 4 6// 输出
// 4
// 说明
// 路线为5->4->5->6->6
//==========================重点====================
// 1. 启发是bfs， 每一步都要考虑一个最大值
// 2. 二维数组存储当前邻居 值 横坐标 纵坐标
// 3. 数组排序
// 4. 取最大邻居里的最小值 更新为答案
const getPath = (r, c, grid) => {let ans = Math.min(grid[0][0], grid[r - 1][c - 1]);const checkList = Array(r).fill(0).map(() => Array(c).fill(0));checkList[0][0] = 1;let isContinueFind = true;const dirs = [[0, 1],[0, -1],[-1, 0],[1, 0],];//   二维数组存储当前邻居 值 横坐标 纵坐标const arr = [[grid[0][0], 0, 0]];while (isContinueFind) {// 排序后取最大的那条路arr.sort((a, b) => a[0] - b[0]);let [curVal, curX, curY] = arr.pop();// 取最小ans = Math.min(ans, curVal);for (let dir of dirs) {let [dx, dy] = dir;let nextX = dx + curX;let nextY = dy + curY;if (nextX >= 0 &&nextX < r &&nextY >= 0 &&nextY < c &&checkList[nextX][nextY] === 0) {if (nextX === r - 1 && nextY === c - 1) {isContinueFind = false;break;}checkList[nextX][nextY] = 1;arr.push([grid[nextX][nextY], nextX, nextY]);}}}return ans;
};
console.log(getPath(3, 3, [[5, 4, 5],[1, 2, 6],[7, 4, 6],])
); // 4

这篇关于算法| DFSBFS套路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---