LeetCode——DFS

谁践踏了优雅 2023-06-19 04:20 100阅读 0赞

# DFS #

--------------------

## 目录 ##

1.  DFS
2.  查找最大的连通面积
3.  矩阵中的连通分量数目
4.  好友关系的连通分量数目
5.  填充封闭区域
6.  能到达的太平洋和大西洋的区域

--------------------

### 1. DFS ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]  
广度优先遍历一层一层遍历，每一层得到的所有新节点，要用队列存储起来以备下一层遍历的时候再遍历。

而深度优先搜索在得到一个新节点时立即对新节点进行遍历：从节点 0 出发开始遍历，得到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如果反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况时，继续对跟节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种`可达性`问题。

在程序实现 DFS 时需要考虑以下问题：

*  栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
 *  标记：和 BFS 一样，同样需要对已经遍历过的节点进行标记。

--------------------

### 2. 查找最大的连通面积 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]

private int m, n;
        private int[][] direction = {
        {
        0, 1}, {
        0, -1}, {
        1, 0}, {
        -1, 0}};
    
        public int maxAreaOfIsland(int[][] grid) {
        
            if (grid == null || grid.length == 0) {
        
                return 0;
            }
            m = grid.length;
            n = grid[0].length;
            int maxArea = 0;
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    maxArea = Math.max(maxArea, dfs(grid, i, j));
                }
            }
            return maxArea;
        }
    
        private int dfs(int[][] grid, int r, int c) {
        
            if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
        
                return 0;
            }
            grid[r][c] = 0;
            int area = 1;
            for (int[] d : direction) {
        
                area += dfs(grid, r + d[0], c + d[1]);
            }
            return area;
        }

--------------------

### 3. 矩阵中的连通分量数目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]  
可以将矩阵表示看成一张有向图。

private int m, n;
        private int[][] direction = {
        {
        0, 1}, {
        0, -1}, {
        1, 0}, {
        -1, 0}};
    
        public int numIslands(char[][] gird) {
        
            if (gird == null || gird.length == 0) {
        
                return 0;
            }
            m = gird.length;
            n = gird[0].length;
            int areas = 0;
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (gird[i][j] != '0') {
        
                        dfs(gird, i, j);
                        areas++;
                    }
                }
            }
            return areas;
        }
    
        private void dfs(char[][] gird, int r, int c) {
        
            if (r < 0 || r >= m || c < 0 || c >= n || gird[r][c] == '0') {
        
                return;
            }
            gird[r][c] = '0';
            for (int[] d : direction) {
        
                dfs(gird, r + d[0], c + d[1]);
            }
        }

--------------------

### 4. 好友关系的连通分量数目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]  
题目描述：好友关系可以看成一个无向图，例如第 0 个人与第 1 个人是好友，那么 M\[0\]\[1\] 和 M\[1\]\[0\] 的值都为1。

private int n;
    
        public int findCircleNum(int[][] M) {
        
            n = M.length;
            int circleNum = 0;
            boolean[] hasVisited = new boolean[n]; //表示是否已经查看某人的朋友关系。
            for (int i = 0; i < n; i++) {
        
                if (!hasVisited[i]) {
        
                    dfs(M, i, hasVisited);
                    circleNum++;
                }
            }
            return circleNum;
        }
    
        private void dfs(int[][] M, int i, boolean[] hasVisited) {
        
            hasVisited[i] = true;
            for (int k = 0; k < n; k++) {
        
                if (M[i][k] == 1 && !hasVisited[k]) {
        
                    dfs(M, k, hasVisited);
                }
            }
        }

--------------------

### 5. 填充封闭区域 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]  
题目描述：使被 ‘X’ 包围的 ‘O’ 转换为 ‘X’。

先填充最外侧，剩下的就是里侧了。

private int[][] direction = {
        {
        0, 1}, {
        0, -1}, {
        1, 0}, {
        -1, 0}};
        int m, n;
    
        public void solve(char[][] board) {
        
            if (board == null || board.length == 0) {
        
                return;
            }
            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';
                    } else if (board[i][j] == 'T') {
        
                        board[i][j] = 'O';
                    }
                }
            }
        }
    
        private void dfs(char[][] board, int r, int c) {
        
            if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
        
                return;
            }
            board[r][c] = 'T';
            for (int[] d : direction) {
        
                dfs(board, r + d[0], c + d[1]);
            }
        }

--------------------

### 6. 能到达的太平洋和大西洋的区域 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 5]  
左边和上边是太平洋，右边和下边是大西洋，内部的数字代表海拔，海拔高的地方的水能够流到低的地方，求解水能够流到太平洋和大西洋的所有位置。

private int m, n;
        private int[][] matrix;
        private int[][] direction = {
        {
        0, 1}, {
        0, -1}, {
        1, 0}, {
        -1, 0}};
    
        public List<int[]> pacificAtlantic(int[][] matrix) {
        
            List<int[]> ret = new ArrayList<>();
            if (matrix == null || matrix.length == 0) {
        
                return ret;
            }
    
            m = matrix.length;
            n = matrix[0].length;
            this.matrix = matrix;
            boolean[][] canReachP = new boolean[m][n];
            boolean[][] canReachA = new boolean[m][n];
    
            for (int i = 0; i < m; i++) {
        
                dfs(i, 0, canReachP);
                dfs(i, n - 1, canReachA);
            }
    
            for (int i = 0; i < n; i++) {
        
                dfs(0, i, canReachP);
                dfs(m - 1, i, canReachA);
            }
    
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (canReachP[i][j] && canReachA[i][j]) {
        
                        ret.add(new int[]{
        i, j});
                    }
                }
            }
            return ret;
        }
    
        private void dfs(int r, int c, boolean[][] canReach) {
        
            if (canReach[r][c]) {
        
                return;
            }
            canReach[r][c] = true;
            for (int[] d : direction) {
        
                int nextR = d[0] + r;
                int nextC = d[1] + c;
                if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n || matrix[r][c] > matrix[nextR][nextC]) {
        
                    continue;
                }
                dfs(nextR, nextC, canReach);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191204143946650.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191204145012737.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191204155802619.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191204165847481.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191204211345210.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191204215906277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70

LeetCode——DFS

发表评论取消回复

还没有评论，来说两句吧...

相关阅读