图论

图论

图论其实就是深度搜索和广度搜索两部分，基本是这两个算法思路在图上的应用。图一般是许多个相互关联的节点组成，相当于多点多连接的链表或者二叉树。因此，遍历图一般就是上述两种思路。

深度优先搜索理论 DFS

深度优先，顾名思义，先是一个方向探到底，再回头进行别的方向的探索。由于这种性质，深度优先dfs本质上就是回溯算法，回溯算法的终止条件，for剪枝等都可以运用在深度算法上。

797. 所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

image-20240116205347259

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    List<List<Integer>> ans;		// 用来存放满足条件的路径
    List<Integer> cnt;		// 用来保存 dfs 过程中的节点值

    //一般回溯函数的形参包括题目所给的形参，也就是int[][] graph，它是一切的基础
    public void dfs(int[][] graph, int node) {
        if (node == graph.length - 1) {		// 如果当前节点是 n - 1，那么就保存这条路径
            ans.add(new ArrayList<>(cnt));
            return;
        }
        for (int index = 0; index < graph[node].length; index++) {
            int nextNode = graph[node][index];
            cnt.add(nextNode);
            dfs(graph, nextNode);
            cnt.remove(cnt.size() - 1);		// 回溯
        }
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        ans = new ArrayList<>();
        cnt = new ArrayList<>();
        cnt.add(0);			// 注意，0 号节点要加入 cnt 数组中
        dfs(graph, 0);
        return ans;
    }
}

广度优先搜索理论

广度搜索和深度搜索形成了比较，深度是一探到底，再回头。广度是先探四周，再往底下深入去探，关键是广度探索的规则，比起深度探索是要复杂些。

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

思路：岛屿问题是经典的图论，一般是用dfs或者bfs解决。该题中，dfs的关键是如何处理索引越界问题，其实就是在索引越界之前，把越界的索引用if检测出来并抛开。另一个关键是使用淹没法，找到一个1就淹没一整片大陆；在bfs中，第一次接触还不熟悉怎么储存已经访问的数据，其实用一个同等大小的boolean数组储存就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//深度搜索解法
class Solution{
    public int numIslands(char[][] grid) {
    int res = 0; //记录找到的岛屿数量
    for(int i = 0;i < grid.length;i++){
        for(int j = 0;j < grid[0].length;j++){
        	//找到“1”，res加一，同时淹没这个岛
            if(grid[i][j] == '1'){
                res++;
                dfs(grid,i,j);
            }
        }
    }
    return res;
}
//使用DFS“淹没”岛屿
    public void dfs(char[][] grid, int i, int j){
        //搜索边界：索引越界或遍历到了"0"
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
        //将这块土地标记为"0"
        grid[i][j] = '0';
        //根据"每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成"，对上下左右的相邻顶点进行dfs
        dfs(grid,i - 1,j);
        dfs(grid,i + 1,j);
        dfs(grid,i,j + 1);
        dfs(grid,i,j - 1);
    }

}
//广度搜索解法
class Solution {
	//用visited数组表示是否访问过，结合bfs，先走遍所有陆地的思想，也相当于dfs的水淹七军
    boolean[][] visited;
    int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	//这里是双重for循环遍历每一个元素，如果已经访问就跳过
    public int numIslands(char[][] grid) {
        int res = 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);
                    res++;
                }
            }
        }
        return res;
    }
	
    //一旦找到陆地，将这片岛屿上的所有陆地都访问到
    public void bfs(char[][] grid, int y, int x) {
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{y, x});
        visited[y][x] = true;
        //用一个队列储存即将访问的陆地
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int m = cur[0];
            int n = cur[1];
            for(int i = 0; i < 4; i++) {
                int nexty = m + move[i][0];
                int nextx = n + move[i][1];
                //处理数组越界问题
                if(nextx < 0 || nexty == grid.length || nexty < 0 || nextx == grid[0].length) continue;
                //如果下一块是尚未访问的陆地，就加入队列，只要加了队列，不用弹出就算已经访问了，因为这可以减少先弹出的元素的遍历成本
                if(!visited[nexty][nextx] && grid[nexty][nextx] == '1') {
                    queue.offer(new int[]{nexty, nextx}); 
                    visited[nexty][nextx] = true; //只要加入队列就标记为访问
                }
            }
        }
    }
}

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

思路：这题和上一题相似，都是遍历到以前没访问的陆地时，跳进递归函数先走遍岛屿。还是需要用一个Boolean数组储存是否访问，唯一不同就是需要用max比较并保存最大的岛屿面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    boolean[][] visited;
    int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int tempRes = 1;
    public int maxAreaOfIsland(int[][] grid) {
        int res = 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);
                    res = Math.max(res, tempRes);
                    tempRes = 1;
                }
            }
        }
        return res;
    }
    public void bfs(int[][] grid, int y, int x){
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{y, x});
        visited[y][x] = true;
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int m = cur[0];
            int n = cur[1];
            for(int i = 0; i < 4; i++){
                int next_y = m + move[i][0];
                int next_x = n + move[i][1];
                if(next_x < 0 || next_y >= grid.length || next_y < 0 || next_x == grid[0].length) continue;
                if(!visited[next_y][next_x] && grid[next_y][next_x] == 1){
                    queue.offer(new int[]{next_y, next_x});
                    visited[next_y][next_x] = true;
                    tempRes++;
                }
            }
        }
    }

}

1020. 飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

思路：这题也是寻岛屿的面积，不过要排除掉能联通边界的岛屿，有一个讨巧的思路，就是先遍历四个边界，这样一定先能找到所有联通边界的岛屿，然后用水淹掉就行。完了再遍历除去四条边的区域，只要有1就可以直接算到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    // 四个方向
    private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    // 广度优先遍历，把可以通向边缘部分的 1 全部标记成 true
    public void bfs(int[][] grid, Queue<int[]> queue, boolean[][] visited) {
        while (!queue.isEmpty()) {
            int[] curPos = queue.poll();
            for (int[] current: position) {
                int row = curPos[0] + current[0], col = curPos[1] + current[1];
                // 下标越界直接跳过
                if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length) 
                    continue;
                // 当前位置不是 1 或者已经被访问了就直接跳过
                if (visited[row][col] || grid[row][col] == 0) continue;
                visited[row][col] = true;
                queue.add(new int[]{row, col});
            }
        }
    }

    public int numEnclaves(int[][] grid) {
        int rowSize = grid.length, colSize = grid[0].length, ans = 0;	// ans 记录答案
        // 标记数组记录每个值为 1 的位置是否可以到达边界，可以为 true，反之为 false
        boolean[][] visited = new boolean[rowSize][colSize];
        Queue<int[]> queue = new ArrayDeque<>();
        // 搜索左侧边界和右侧边界查找 1 存入队列
        for (int row = 0; row < rowSize; row++) {
            if (grid[row][0] == 1) {
                visited[row][0] = true;
                queue.add(new int[]{row, 0});
            }
            if (grid[row][colSize - 1] == 1) {
                visited[row][colSize - 1] = true;
                queue.add(new int[]{row, colSize - 1});
            }
        }
        // 搜索上边界和下边界遍历，但是四个角不用遍历，因为上面已经遍历到了
        for (int col = 1; col < colSize - 1; col++) {
            if (grid[0][col] == 1) {
                visited[0][col] = true;
                queue.add(new int[]{0, col});
            }
            if (grid[rowSize - 1][col] == 1 && !visited[rowSize - 1][col]) {
                visited[rowSize - 1][col] = true;
                queue.add(new int[]{rowSize - 1, col});
            }
        }
        bfs(grid, queue, visited);		// 广度优先遍历
        // 查找没有标记过的 1，记录到 ans 中
        for (int row = 0; row < rowSize; row++) {
            for (int col = 0; col < colSize; col++) {
                if (grid[row][col] == 1 && !visited[row][col]) ++ans;
            }
        }
        return ans;
    }
}

130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

image-20240120222505753

思路：这题就是飞地数量的翻版，还是先遍历四条边，然后用visited数组储存能联通的区域。而对于除去四条边的区域，没有visited又是陆地的，直接淹掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 广度优先遍历
// 使用 visited 数组进行标记
class Solution {
    private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  // 四个方向

    public void solve(char[][] board) {
        // rowSize：行的长度，colSize：列的长度
        int rowSize = board.length, colSize = board[0].length; 
        boolean[][] visited = new boolean[rowSize][colSize];
        Queue<int[]> queue = new ArrayDeque<>();
        // 从左侧边，和右侧边遍历
        for (int row = 0; row < rowSize; row++) {
            if (board[row][0] == 'O') {
                visited[row][0] = true;
                queue.add(new int[]{row, 0});
            }
            if (board[row][colSize - 1] == 'O') {
                visited[row][colSize - 1] = true;
                queue.add(new int[]{row, colSize - 1});
            }
        }
        // 从上边和下边遍历，在对左侧边和右侧边遍历时我们已经遍历了矩阵的四个角
        // 所以在遍历上边和下边时可以不用遍历四个角
        for (int col = 1; col < colSize - 1; col++) {
            if (board[0][col] == 'O') {
                visited[0][col] = true;
                queue.add(new int[]{0, col});
            }
            if (board[rowSize - 1][col] == 'O') {
                visited[rowSize - 1][col] = true;
                queue.add(new int[]{rowSize - 1, col});
            }
        }
        // 广度优先遍历，把没有被 'X' 包围的 'O' 进行标记
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            for (int[] pos: position) {
                int row = current[0] + pos[0], col = current[1] + pos[1];
                // 如果范围越界、位置已被访问过、该位置的值不是 'O'，就直接跳过
                if (row < 0 || row >= rowSize || col < 0 || col >= colSize) continue;
                if (visited[row][col] || board[row][col] != 'O') continue;
                visited[row][col] = true;
                queue.add(new int[]{row, col});
            }
        }
        // 遍历数组，把没有被标记的 'O' 修改成 'X'
        for (int row = 0; row < rowSize; row++) {
            for (int col = 0; col < colSize; col++) {
                if (board[row][col] == 'O' && !visited[row][col]) board[row][col] = 'X';
            }
        }
    }
}

417. 太平洋大西洋水流问题

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

image-20240121111114960

思路：这题使用bfs遍历每一个元素，如果可以同时到达左上和右下两个边界，那么就加入res。但是这种方法比较耗时，我们反向思维，从两个海洋的边界出发逆流而上，并使用标记数组visited，取两者的交叉点，就是答案数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    // 四个位置
    private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    /**
     * @param heights 题目给定的二维数组
     * @param queue 记录可以到达边界的节点
     * @param visited 记录这个位置可以到哪条河
     */
    public void bfs(int[][] heights, Queue<int[]> queue, boolean[][][] visited) {
        while (!queue.isEmpty()) {
            int[] curPos = queue.poll();
            for (int[] current: position) {
                int row = curPos[0] + current[0], col = curPos[1] + current[1], sign = curPos[2];
                // 越界
                if (row < 0 || row >= heights.length || col < 0 || col >= heights[0].length) continue;
                // 高度不合适或者已经被访问过了
                if (heights[row][col] < heights[curPos[0]][curPos[1]] || visited[row][col][sign]) continue;
                visited[row][col][sign] = true;
                queue.add(new int[]{row, col, sign});
            }
        }
    }

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int rowSize = heights.length, colSize = heights[0].length;
        List<List<Integer>> ans = new ArrayList<>();
        boolean[][][] visited = new boolean[rowSize][colSize][2];
        // 队列，保存的数据为 [行号, 列号, 标记]
        // 假设太平洋的标记为 1，大西洋为 0
        Queue<int[]> queue = new ArrayDeque<>();
        for (int row = 0; row < rowSize; row++) {
            visited[row][colSize - 1][0] = true;
            visited[row][0][1] = true;
            queue.add(new int[]{row, colSize - 1, 0});
            queue.add(new int[]{row, 0, 1});
        }
        for (int col = 0; col < colSize; col++) {
            visited[rowSize - 1][col][0] = true;
            visited[0][col][1] = true;
            queue.add(new int[]{rowSize - 1, col, 0});
            queue.add(new int[]{0, col, 1});
        }
        bfs(heights, queue, visited);
        for (int row = 0; row < rowSize; row++) {
            for (int col = 0; col < colSize; col++) {
                // 如果该位置即可以到太平洋又可以到大西洋，就放入答案数组
                if (visited[row][col][0] && visited[row][col][1])
                    ans.add(List.of(row, col));
            }
        }
        return ans;
    }
}

827. 最大人工岛

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

思路：这题的暴力解法很直观，就是遍历每一个0，然后在每一个0 dfs，判断新岛屿的面积大小。但这种解法非常慢，因为岛屿会在其周边的每一个0都遍历一次，其实这是没必要的。优化思路：先遍历一遍所有的岛屿，遍历过程记录每个岛屿的面积，并且将每个岛屿的值改成岛屿的编号，用一个key-value的hashmap来维护岛屿编号和岛屿面积。之后遍历0就行，0只需要遍历上下左右四个方向临近有没有岛，加上相邻的岛值，然后取最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  // 四个方向

    public int dfs(int[][] grid, int row, int col, int mark) {
        int ans = 0;
        grid[row][col] = mark;
        for (int[] current: position) {
            int curRow = row + current[0], curCol = col + current[1];
            if (curRow < 0 || curRow >= grid.length || curCol < 0 || curCol >= grid.length) continue;  // 越界
            if (grid[curRow][curCol] == 1)
                ans += 1 + dfs(grid, curRow, curCol, mark);
        }
        return ans;
    }

    public int largestIsland(int[][] grid) {
        int ans = Integer.MIN_VALUE, size = grid.length, mark = 2;
        Map<Integer, Integer> getSize = new HashMap<>();
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                if (grid[row][col] == 1) {
                    int areaSize = 1 + dfs(grid, row, col, mark);
                    getSize.put(mark++, areaSize);
                }
            }
        }
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                // 当前位置如果不是 0 那么直接跳过，因为我们只能把 0 变成 1
                if (grid[row][col] != 0) continue;
                Set<Integer> hashSet = new HashSet<>();     // 防止同一个区域被重复计算
                // 计算从当前位置开始获取的 1 的数量，初始化 1 是因为把当前位置的 0 转换成了 1 
                int curSize = 1;
                for (int[] current: position) {
                    int curRow = row + current[0], curCol = col + current[1];
                    if (curRow < 0 || curRow >= grid.length || curCol < 0 || curCol >= grid.length) continue;
                    int curMark = grid[curRow][curCol];     // 获取对应位置的标记
                    // 如果标记存在 hashSet 中说明该标记被记录过一次，如果不存在 getSize 中说明该标记是无效标记(此时 curMark = 0)
                    if (hashSet.contains(curMark) || !getSize.containsKey(curMark)) continue;
                    hashSet.add(curMark);
                    curSize += getSize.get(curMark);
                }
                ans = Math.max(ans, curSize);
            }
        }
        // 当 ans == Integer.MIN_VALUE 说明矩阵数组中不存在 0，全都是有效区域，返回数组大小即可
        return ans == Integer.MIN_VALUE ? size * size : ans;
    }
}

127. 单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

  • 每一对相邻的单词只差一个字母。
  • 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

思路：这道题明显是一个无向搜索，那么就一定要使用标记位来记录以访问元素，防止重复访问造成死循环；求的是最短序列，那么就要使用bfs来解，这样解出来就是最短的序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> wordSet = new HashSet<>(wordList); //转换为hashset 加快速度
        if (wordSet.size() == 0 || !wordSet.contains(endWord)) {  //特殊情况判断
            return 0;
        }
        Queue<String> queue = new LinkedList<>(); //bfs 队列
        queue.offer(beginWord);
        Map<String, Integer> map = new HashMap<>(); //记录单词对应路径长度
        map.put(beginWord, 1);

        while (!queue.isEmpty()) {
            String word = queue.poll(); //取出队头单词
            int path  = map.get(word); //获取到该单词的路径长度
            for (int i = 0; i < word.length(); i++) { //遍历单词的每个字符
                char[] chars = word.toCharArray(); //将单词转换为char array，方便替换
                for (char k = 'a'; k <= 'z'; k++) { //从'a' 到 'z' 遍历替换
                    chars[i] = k; //替换第i个字符
                    String newWord = String.valueOf(chars); //得到新的字符串
                    if (newWord.equals(endWord)) {  //如果新的字符串值与endWord一致，返回当前长度+1
                        return path + 1;
                    }
                    if (wordSet.contains(newWord) && !map.containsKey(newWord)) { //如果新单词在set中，但是没有访问过
                        map.put(newWord, path + 1); //记录单词对应的路径长度
                        queue.offer(newWord);//加入队尾
                    }
                }
            }
        }
        return 0; //未找到
    }
}

841. 钥匙和房间

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

思路：这道题需要判断能不能进入，那么采用dfs会更好，bfs一般是用在最短路径的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    boolean[] visited;
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int[][] roomsArray = new int[rooms.size()][];
        for (int i = 0; i < rooms.size(); i++) {
            List<Integer> room = rooms.get(i);
            // 初始化当前行的数组
            roomsArray[i] = new int[room.size()];
            for (int j = 0; j < room.size(); j++) {
                // 将 Integer 转换为 int
                roomsArray[i][j] = room.get(j);
            }
        }
        visited = new boolean[roomsArray.length];
        Deque<Integer> deque = new ArrayDeque<>();
        for(int key : roomsArray[0]){
            deque.add(key);
            visited[0] = true;
        }
        while(!deque.isEmpty()){
            int curKey = deque.poll();
            visited[curKey] = true;
            for(int nextKey : roomsArray[curKey]){
                if(!visited[nextKey]){
                    deque.add(nextKey);
                    visited[nextKey] = true;
                }
            }
        }
        for(boolean temp : visited){
            if(!temp){
                return false;
            }
        }
        return true;
    }
}

1971. 寻找图中是否存在路径

有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。

给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。

思路：这道题是经典的并查集，先初始化，然后join加入节点关系，通过find进行路径压缩。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    //并查集记录父节点的数组，当中的元素代表该序号指向的根节点，也就是不同的集合
    int[] father;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        father = new int[n];
        //初始化要设置每个序号的根节点是自身，也就是n个集合
        init();
        //这里是逐个遍历edges，加入并查集
        for (int i = 0; i < edges.length; i++) {
            join(edges[i][0], edges[i][1]);
        }

        return isSame(source, destination);
    }

    // 并查集初始化
    public void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
    }

    // 并查集里寻根的过程
    public int find(int u) {
        if (u == father[u]) {
            return u;
        } else {
            father[u] = find(father[u]);
            return father[u];
        }
    }

    // 判断 u 和 v是否找到同一个根
    public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    // 将v->u 这条边加入并查集
    public void join(int u, int v) {
        u = find(u); // 寻找u的根
        v = find(v); // 寻找v的根
        // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        if (u == v) return; 
        //根不同，就是两个集合，此时v指向u，融为一体
        father[v] = u;
    }

}

684. 冗余连接

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

image-20240125162330869

思路：经典并查集问题，删除后节点数量不变，也就是说明删除的这条边，一定在环上。返回最后出现那条边，则说明了连成环的最后一条边，那么正常从前到后遍历就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    int[] father;
    public int[] findRedundantConnection(int[][] edges) {
        father = new int[edges.length + 1];
        init();
        for(int[] cur : edges){
            if(find(cur[0]) == find(cur[1])){
                return cur;
            }else{
                join(cur[0], cur[1]);
            }
        }
        return null;
    }
    public void init(){
        for(int i = 0; i < father.length; i++){
            father[i] = i;
        }
    }
    public void join(int cur1, int cur2){
        cur1 = find(cur1);
        cur2 = find(cur2);
        if(cur1 == cur2) return;
        father[cur2] = cur1;
    }
    public int find(int index){
        if(index == father[index]){
            return index;
        }else{
            father[index] = find(father[index]);
            return father[index];
        }
    }
}

685. 冗余连接 II

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

image-20240125165940305

思路：这题是有向的图，如果都是单方向的还好，那么思路和上一题的就一样了。区别点在于，在有向的图中，当一个节点的入度大于1，那么这一定是一个环，就看剪掉哪条边。剪掉哪边取决于剩下的图是否构成树，如果是环，那么就一定不是树，反之就是环。

这题思路复杂，伪代码如下：

1
2
3
4
5
6
7
8
9
if(存在入度大于1){
	if(剪1，剩下图构成有向环){
		return 2;
	}else{
		return 1;
	}
}else{
	上一题并查集典型操作；
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class Solution {

    private static final int N = 1010;  // 如题：二维数组大小的在3到1000范围内
    private int[] father;
    public Solution() {
        father = new int[N];

        // 并查集初始化
        for (int i = 0; i < N; ++i) {
            father[i] = i;
        }
    }

    // 并查集里寻根的过程
    private int find(int u) {
        if(u == father[u]) {
            return u;
        }
        father[u] = find(father[u]);
        return father[u];
    }

    // 将v->u 这条边加入并查集
    private void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return ;
        father[v] = u;
    }

    // 判断 u 和 v是否找到同一个根
    private Boolean same(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    /**
     * 初始化并查集
     */
    private void initFather() {
        // 并查集初始化
        for (int i = 0; i < N; ++i) {
            father[i] = i;
        }
    }

    /**
     * 在有向图里找到删除的那条边，使其变成树
     * @param edges
     * @return 要删除的边
     */
    private int[] getRemoveEdge(int[][] edges) {
        initFather();
        for(int i = 0; i < edges.length; i++) {
            if(same(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
                return edges[i];
            }
            join(edges[i][0], edges[i][1]);
        }
        return null;
    }

    /**
     * 删一条边之后判断是不是树
     * @param edges
     * @param deleteEdge 要删除的边
     * @return  true: 是树， false： 不是树
     */
    private Boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge)
    {
        initFather();
        for(int i = 0; i < edges.length; i++)
        {
            if(i == deleteEdge) continue;
            if(same(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
                return false;
            }
            join(edges[i][0], edges[i][1]);
        }
        return true;
    }

    public int[] findRedundantDirectedConnection(int[][] edges) {
        int[] inDegree = new int[N];
        for(int i = 0; i < edges.length; i++)
        {
            // 入度
            inDegree[ edges[i][1] ] += 1;
        }

        // 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案
        ArrayList<Integer> twoDegree = new ArrayList<Integer>();
        for(int i = edges.length - 1; i >= 0; i--)
        {
            if(inDegree[edges[i][1]] == 2) {
                twoDegree.add(i);
            }
        }

        // 处理图中情况1 和 情况2
        // 如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树
        if(!twoDegree.isEmpty())
        {
            if(isTreeAfterRemoveEdge(edges, twoDegree.get(0))) {
                return edges[ twoDegree.get(0)];
            }
            return edges[ twoDegree.get(1)];
        }

        // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
        return getRemoveEdge(edges);
    }
}
算法
#算法 #刷题
图论
https://wengerblogs.me/2025/05/13/图论/
Author
Wenger
Posted on
May 13, 2025
Licensed under