图论算法学习

图论

• 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[p+1..]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) {Queue<Node> q; // 核心数据结构Set<Node> 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;Queue<TreeNode> 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;Queue<int[]> 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 (r+1 < M && grid[r+1][c] == 1) {grid[r+1][c] = 2;count--;queue.add(new int[]{r+1, c});}// ← 左邻点 同上if (c-1 >= 0 && grid[r][c-1] == 1) {grid[r][c-1] = 2;count--;queue.add(new int[]{r, c-1});}// → 右邻点 同上if (c+1 < N && grid[r][c+1] == 1) {grid[r][c+1] = 2;count--;queue.add(new int[]{r, c+1});}}}// 如果此时还有健康的橘子// 返回 -1// 否则 返回层级if (count > 0) {return -1;} else {return round;}}
}