力扣爆刷第145天之图论五连刷（dfs和bfs）

力扣爆刷第145天之图论五连刷（dfs和bfs）

总结

dfs是一条路走到底，类似于树的遍历，即一直递归，直至终点。
bfs是一圈一圈的往外遍历，类似于树的水平遍历，一般使用队列来做。（bfs适合来求两点之间的最短路径）。

一、797. 所有可能的路径

题目链接：https://leetcode.cn/problems/all-paths-from-source-to-target/description/
思路：本题求所有可能的路径，从0到n-1节点的路径，本题是有向无环图，让我们搜索所有的路径，本质上和遍历树没啥区别，只不过是多叉树，寻找路径自然是深度优先，为了能在递归返回时再记录其他的路径，自然要使用回溯，那么本题就是dfs然后加上回溯，本质上来说，回溯也是深度优先。不过本题是有向无环图，且定向路径，不需要去重。

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> allPathsSourceTarget(int[][] graph) {list.add(0);dfs(graph, 0);return result;}void dfs(int[][] graph, int start) {if(graph.length-1 == start) {result.add(new ArrayList(list));return;}for(int i = 0; i < graph[start].length; i++) {list.add(graph[start][i]);dfs(graph, graph[start][i]);list.remove(list.size()-1);}}
}

二、200. 岛屿数量

题目链接：https://leetcode.cn/problems/number-of-islands/description/
思路：dfs和bfs都可以，这里使用dfs，外部遍历，只要是岛屿就计数并进行dfs，在进行dfs的过程中，只要是岛屿就设置为海洋，然后向周围四个方向进行dfs，这样一次递归返回，即可标记一个岛。

class Solution {public int numIslands(char[][] grid) {int sum = 0;for(int i = 0; i < grid.length; i++) {for(int j = 0; j < grid[0].length; j++) {if(grid[i][j] == '1') {dfs(grid, i, j);sum++;}}}return sum;}void dfs(char[][] grid, int x, int y) {if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0') return ;grid[x][y] = '0';dfs(grid, x+1, y);dfs(grid, x-1, y);dfs(grid, x, y+1);dfs(grid, x, y-1);}}

三、695. 岛屿的最大面积

题目链接：https://leetcode.cn/problems/max-area-of-island/description/
思路：求岛屿的最大面积和上一题是类似，上一题是求岛屿的数量，本题只需要在每一次对一个岛屿进行dfs时进行累加，遍历完再记录最大值，清空记录值，以此往复即可。

class Solution {int max = 0, k = 0;public int maxAreaOfIsland(int[][] grid) {for(int i = 0; i < grid.length; i++) {for(int j = 0; j < grid[0].length; j++) {if(grid[i][j] == 1) {k = 0;dfs(grid, i, j);max = Math.max(max, k);}}}return max;}void dfs(int[][] grid, int x, int y) {if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) return;k++;grid[x][y] = 0;dfs(grid, x-1, y);dfs(grid, x+1, y);dfs(grid, x, y-1);dfs(grid, x, y+1); }
}

四、1020. 飞地的数量

题目链接：https://leetcode.cn/problems/number-of-enclaves/description/
思路：求飞地的数量，本题也是dfs，看看只要掌握了dfs常见的图论的题目都可以做，本题对飞地的顶用是不与边界接壤的土地，本质上还是求所有岛屿的面积，只不过在记录的过程中需要一个标志位记录该岛屿是否是飞地，只有是飞地，面积才会累加。

class Solution {boolean flag = true;int count = 0, k = 0;public int numEnclaves(int[][] grid) {for(int i = 0; i < grid.length; i++) {for(int j = 0; j < grid[0].length; j++) {if(grid[i][j] == 1) {k = 0;flag = true;dfs(grid, i, j);if(flag) count += k; }}}return count;}void dfs(int[][] grid, int x, int y) {if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) return;if(x == 0 || x == grid.length-1 || y == 0 || y == grid[0].length-1) flag = false;k++;grid[x][y] = 0;dfs(grid, x-1, y);dfs(grid, x+1, y);dfs(grid, x, y-1);dfs(grid, x, y+1);}
}

五、130. 被围绕的区域

题目链接：https://leetcode.cn/problems/surrounded-regions/description/
思路：也是经典的海岛问题，和上一题不一样的是，让把节点相接壤的区域给保留下来，只需要先沿着边界递归，把与边界相接壤的岛屿先设置为一种标记，然后全文遍历，把不接壤的设置为海洋，再把接壤的给还原回来。

class Solution {public void solve(char[][] board) {int m = board.length, n = board[0].length;for(int i = 0; i < m; i++) {dfs(board, i, 0);dfs(board, i, n-1);}for(int i = 0; i < n; i++) {dfs(board, 0, i);dfs(board, m-1, i);}for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(board[i][j] == 'O') board[i][j] = 'X';if(board[i][j] == 'A') board[i][j] = 'O';}}}void dfs(char[][] board, int x, int y) {if(x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != 'O') return;board[x][y] = 'A';dfs(board, x-1, y);dfs(board, x+1, y);dfs(board, x, y-1);dfs(board, x, y+1);}
}