帮齐家网做的网站,做网站建网站,网站建设前台功能,想接做网站的单子图论
dfs是可一个方向去搜#xff0c;不到黄河不回头#xff0c;直到遇到绝境了#xff0c;搜不下去了#xff0c;再换方向#xff08;换方向的过程就涉及到了回溯#xff09;。bfs是先把本节点所连接的所有节点遍历一遍#xff0c;走到下一个节点的时候#xff0c;再…图论
dfs是可一个方向去搜不到黄河不回头直到遇到绝境了搜不下去了再换方向换方向的过程就涉及到了回溯。bfs是先把本节点所连接的所有节点遍历一遍走到下一个节点的时候再把连接节点的所有节点遍历一遍搜索方向更像是广度四面八方的搜索过程。
DFS
如何在二维矩阵中使用 DFS 搜索呢如果你把二维矩阵中的每一个位置看做一个节点这个节点的上下左右四个位置就是相邻节点那么整个矩阵就可以抽象成一幅网状的「图」结构。
DFS (Depth-First Search) 是一种图遍历算法用于探索或搜索图或树的节点。该算法从起始节点开始尽可能深地探索每个分支直到遇到没有未探索邻居的节点然后回溯到上一个未探索的节点并继续探索其他分支。这个过程一直持续到所有节点都被访问为止。
因为二维矩阵本质上是一幅「图」所以遍历的过程中需要一个visited 布尔数组防止走回头路如果你能理解下面这段代码那么搞定所有岛屿系列题目都很简单。
二维矩阵遍历框架
// 二叉树遍历框架
void traverse(TreeNode root) {traverse(root.left);traverse(root.right);
}
//-------------------------------
// 二维矩阵遍历框架
void dfs(int[][] grid, int i, int j, boolean[][] visited) {//行和列int m grid.length, n grid[0].length;if (i 0 || j 0 || i m || j n) {// 超出索引边界return;}if (visited[i][j]) {// 已遍历过 (i, j)return;}// 进入节点 (i, j)visited[i][j] true;dfs(grid, i - 1, j, visited); // 上dfs(grid, i 1, j, visited); // 下dfs(grid, i, j - 1, visited); // 左dfs(grid, i, j 1, visited); // 右
}
岛屿数量
给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
class Solution {// 主函数计算岛屿数量int numIslands(char[][] grid) {int res 0;int m grid.length, n grid[0].length;// 遍历 gridfor (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {// 每发现一个岛屿岛屿数量加一res;// 然后使用 DFS 将岛屿淹了 与1相连的所有1 变为零 集体是一个岛屿dfs(grid, i, j);// 上下左右都淹了}}}return res;}// 从 (i, j) 开始将与之相邻的陆地都变成海水void dfs(char[][] grid, int i, int j) {int m grid.length, n grid[0].length;// 参数是否正常if (i 0 || j 0 || i m || j n) {// 超出索引边界return;}if (grid[i][j] 1) {grid[i][j] 0;} else {return;}// 淹没上下左右的陆地dfs(grid, i 1, j);dfs(grid, i, j 1);dfs(grid, i - 1, j);dfs(grid, i, j - 1);}
}
为什么每次遇到岛屿都要用 DFS 算法把岛屿「淹了」呢主要是为了省事避免维护 visited 数组。
因为 dfs 函数遍历到值为 0 的位置会直接返回所以只要把经过的位置都设置为 0就可以起到不走回头路的作用。
单词搜索DFS算法 回溯算法
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。
单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
grid.length 返回 grid 数组的长度即行数。grid[0].length 返回 grid 数组的第一行的长度即列数。
class Solution {boolean found false;public boolean exist(char[][] board, String word) {int m board.length, n board[0].length;for (int i 0; i m; i) {for (int j 0; j n; j) {dfs(board, i, j, word, 0);if (found) {return true;}}}return false;}// 从 (i, j) 开始向四周搜索试图匹配 word[p..]void dfs(char[][] board, int i, int j, String word, int p) {if (p word.length()) {// 整个 word 已经被匹配完找到了一个答案found true;return;}if (found) {// 已经找到了一个答案不用再搜索了return;}int m board.length, n board[0].length;if (i 0 || j 0 || i m || j n) {return;}if (board[i][j] ! word.charAt(p)) {return;}// 已经匹配过的字符我们给它添一个负号作为标记避免走回头路board[i][j] (char)(-board[i][j]);// word[p] 被 board[i][j] 匹配开始向四周搜索 word[p1..]dfs(board, i 1, j, word, p 1);dfs(board, i, j 1, word, p 1);dfs(board, i - 1, j, word, p 1);dfs(board, i, j - 1, word, p 1);board[i][j] (char)(-board[i][j]);}
}
BFS
广搜bfs是一圈一圈的搜索过程和深搜dfs是一条路跑到黑然后再回溯。
广搜的搜索方式就适合于解决两个点之间的最短路径问题。
从起点出发每次都尝试访问同一层的节点如果同一层都访问完了再访问下一层最后广度优先搜索找到的路径就是从起点开始的最短合法路径。
使用队列
代码框架
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {QueueNode q; // 核心数据结构SetNode visited; // 避免走回头路q.offer(start); // 将起点加入队列visited.add(start);while (q not empty) {int sz q.size();/* 将当前队列中的所有节点向四周扩散 */for (int i 0; i sz; i) {Node cur q.poll();/* 划重点这里判断是否到达终点 */if (cur is target)return step;/* 将 cur 的相邻节点加入队列 */for (Node x : cur.adj()) {if (x not in visited) {q.offer(x);visited.add(x);}}}}// 如果走到这里说明在图中没有找到目标节点
}
队列 q 就不说了BFS 的核心数据结构cur.adj() 泛指 cur 相邻的节点比如说二维数组中cur 上下左右四面的位置就是相邻节点visited 的主要作用是防止走回头路大部分时候都是必须的但是像一般的二叉树结构没有子节点到父节点的指针不会走回头路就不需要 visited。
二叉树的最小高度
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 起点就是 root 根节点终点就是最靠近根节点的那个「叶子节点」
class Solution {public int minDepth(TreeNode root) {if (root null)return 0;QueueTreeNode q new LinkedList();q.offer(root);// root 本身就是一层depth 初始化为 1int depth 1;while (!q.isEmpty()) {int sz q.size();/* 将当前队列中的所有节点向四周扩散 */for (int i 0; i sz; i) {TreeNode cur q.poll();/* 判断是否到达终点 */if (cur.left null cur.right null)return depth;/* 将 cur 的相邻节点加入队列 */if (cur.left ! null)q.offer(cur.left);if (cur.right ! null)q.offer(cur.right);}/* 这里增加步数 */depth;}return depth;}
}
腐烂的橘子
上下左右相邻的新鲜橘子就是该腐烂橘子尝试访问的同一层的节点路径长度就是新鲜橘子被腐烂的时间。我们记录下每个新鲜橘子被腐烂的时间最后如果单元格中没有新鲜橘子腐烂所有新鲜橘子所必须经过的最小分钟数就是新鲜橘子被腐烂的时间的最大值。
一开始我们找出所有腐烂的橘子将它们放入队列作为第 0 层的结点。然后进行 BFS 遍历每个结点的相邻结点可能是上、下、左、右四个方向的结点注意判断结点位于网格边界的特殊情况。由于可能存在无法被污染的橘子我们需要记录新鲜橘子的数量。在 BFS 中每遍历到一个橘子污染了一个橘子就将新鲜橘子的数量减一。如果 BFS 结束后这个数量仍未减为零说明存在无法被污染的橘子。Count 统计多少橘子
class Solution {public int orangesRotting(int[][] grid) {// 边界 长宽int M grid.length;int N grid[0].length;Queueint[] queue new LinkedList();//每一个元素都是一个一维数组 行和列// count 表示新鲜橘子的数量int count 0; // 遍历二维数组 找出所有的新鲜橘子和腐烂的橘子for (int r 0; r M; r) {for (int c 0; c N; c) {// 新鲜橘子计数if (grid[r][c] 1) {count;// 腐烂的橘子就放进队列} else if (grid[r][c] 2) {// 缓存腐烂橘子的坐标queue.add(new int[]{r, c});}}}// round 表示腐烂的轮数或者分钟数int round 0; // 如果有新鲜橘子 并且 队列不为空// 直到上下左右都触及边界 或者 被感染的橘子已经遍历完while (count 0 !queue.isEmpty()) {// BFS 层级 1round;// 拿到当前层级的腐烂橘子数量 因为每个层级会更新队列int n queue.size();// 遍历当前层级的队列for (int i 0; i n; i) {// 踢出队列拿出一个腐烂的橘子int[] orange queue.poll();// 恢复橘子坐标int r orange[0];int c orange[1];// ↑ 上邻点 判断是否边界 并且 上方是否是健康的橘子if (r-1 0 grid[r-1][c] 1) {// 感染它 grid[r-1][c] 2;// 好橘子 -1 count--;// 把被感染的橘子放进队列 并缓存queue.add(new int[]{r-1, c});}// ↓ 下邻点 同上if (r1 M grid[r1][c] 1) {grid[r1][c] 2;count--;queue.add(new int[]{r1, c});}// ← 左邻点 同上if (c-1 0 grid[r][c-1] 1) {grid[r][c-1] 2;count--;queue.add(new int[]{r, c-1});}// → 右邻点 同上if (c1 N grid[r][c1] 1) {grid[r][c1] 2;count--;queue.add(new int[]{r, c1});}}}// 如果此时还有健康的橘子// 返回 -1// 否则 返回层级if (count 0) {return -1;} else {return round;}}
}
