代码随想录图论第一天|797.所有可能的路径200.岛屿数量

代码随想录图论 第一天 | 797.所有可能的路径 200. 岛屿数量 一、797.所有可能的路径

题目链接： leetcode /problems/all-paths-from-source-to-target/ 思路：求从0到n-1的所有路径，终止条件是当前节点为n-1。本题图的结构是group[][]，group[x]表示x节点所能到达的所有节点的集合，深度优先做本题会一路向下搜索，到头后回溯。

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

题目链接： leetcode /problems/number-of-islands/

深搜：当前节点为1时岛屿数加1，然后把当前节点设置为0，并从当前节点开始进行上下左右四个方向的深度搜索，只要没越界，不是0，那就是相连的就都设置为0，直到递归结束，然后外层遍历开始寻找下一个为1的岛屿。

class Solution { public int numIslands(char[][] grid) { int num = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { num++; dfs(grid, i, j); } } } return num; } 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); } }

广搜：广度优先需要额外有一个标记数组和队列，如果当前节点未遍历过，且为1，进行广度优先搜索，入队，出队，每个出队节点只搜索4个位置，即当前节点是上下左右，只要没超范围而且是1就可以入队，入队后要进行标记，直到该次广搜结束，岛屿数量加1.

class Solution { // 上下左右 int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; boolean[][] visited; public int numIslands(char[][] grid) { int num = 0; visited = new boolean[grid.length][grid[0].length]; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (!visited[i][j] && grid[i][j] == '1') { bfs(grid, i, j); num++; } } } return num; } void bfs(char[][] grid, int x, int y) { Deque<int[]> queue = new LinkedList<>(); queue.offer(new int[]{x, y}); visited[x][y] = true; while (!queue.isEmpty()) { int[] cur = queue.poll(); int m = cur[0], n = cur[1]; for (int i = 0; i < move.length; i++) { int nextX = m + move[i][0]; int nextY = n + move[i][1]; if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue; if (!visited[nextX][nextY] && grid[nextX][nextY] == '1'){ queue.offer(new int[]{nextX, nextY}); visited[nextX][nextY] = true; } } } } }