【经典专题】图论两则——并查集/DFS/BFS/Dijkstra_并查集 dfs

作者：IT小白 | 2024-06-09 19:39:45

踩

并查集 dfs

最小阶梯的远足活动

你参加了一次远足活动，并且有一张地图。

地图是一个矩阵，height[i][j] 表示格子 (i, j)的高度。你有一个习惯，那就是在整段旅途中你不想走落差较大的阶梯，也就是说，一整条路径耗费的体力值是旅途中高度差绝对值的最大值决定的。

请你返回从左上角走到右下角的最小体力消耗值。

注：1 <= rows, columns <= 100，1 <= heights[i][j] <= 10^6

方法一——并查集

这是个很巧妙的「连通」思想。首先将点的矩阵转化为边的集合（这一步可以当作模板记住），然后将这些边按所谓高度差绝对值由小到大排序（排序很关键）；这些点看作一个个孤立的点（并查集初始化），然后用这些已排序的边一条条连通它们（并查集union操作），当左上角与右下角连通时即找到了最终答案。

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int R = heights.length;         // 几行
        int C = heights[0].length;      // 几列
        int LEN = R * C;

        // 将点矩阵转换为边的集合，边的格式为(点1，点2，边的权值)
        List<int[]> edges = new ArrayList<>();
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                int id = i * C + j;
                if(i > 0) {
                    edges.add(new int[]{id, id - C, Math.abs(heights[i][j] - heights[i - 1][j])});
                }
                if(j > 0) {
                    edges.add(new int[]{id, id - 1, Math.abs(heights[i][j] - heights[i][j - 1])});
                }
            }
        }

        // 按权重由小到大进行排序
        Collections.sort(edges, (Comparator.comparingInt(o -> o[2])));

        // 一个一个边(已排序)连接上，即并查集合并操作，当左上角与右下角连通时即找到了整个所谓"最小值"
        UnionSet unionSet = new UnionSet(LEN);
        for (int[] edge : edges) {
            unionSet.union(edge[0], edge[1]);
            if(unionSet.isUnion(0, LEN - 1)) {
                return edge[2];
            }
        }
        return 0;
    }
}

/**
 * 并查集模板
 */
class UnionSet {

    int[] roots;

    public UnionSet(int len) {
        roots = new int[len];
        for(int i = 0; i < len; i++) {
            roots[i] = i;
        }
    }

    public int findRoot(int node) {
        if(roots[node] == node) {
            return node;
        }
        roots[node] = findRoot(roots[node]);
        return roots[node];
    }

    public void union(int node1, int node2) {
        roots[findRoot(node1)] = findRoot(node2);
    }

    public boolean isUnion(int node1, int node2) {
        return findRoot(node1) == findRoot(node2);
    }

}
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

>>> 时间复杂度：点阵转化为边集是"O(mn)"，边的排序是"O(mnlog(mn))"，并查集是"O(mnα(mn))"其中α函数是阿克曼函数的反函数，其渐进意义小于log。综上，时间复杂度是"O(mnlog(mn))"

>>> 空间复杂度：显然是"O(mn)"
1
2
3

方法二——二分法+BFS/DFS

我们已知这个高度差最大值的最小值(0)和最大值(999999)，二分法呼之欲出。每次取的mid值作为高度差最大值（即本次图的遍历的限制条件），看看能否从左上角到达右下角(DFS/BFS)。并以此为依据进行二分。

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int R = heights.length;         // 几行
        int C = heights[0].length;      // 几列
        int LEN = R * C;

        int left = 0;
        int right = 999999;
        int res = 0;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (left <= right) {
            int mid = (left + right) / 2;
            // 每次取到一次mid后，开始BFS >_<
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{0, 0});
            boolean[] visited = new boolean[LEN];
            visited[0] = true;
            while (!queue.isEmpty()) {
                int[] point = queue.poll();
                int row = point[0];
                int col = point[1];
                for(int[] direction : directions) {
                    int newRow = row + direction[0];
                    int newCol = col + direction[1];
                    int newId = newRow * C + newCol;
                    if(newRow >= 0 && newRow < R && newCol >= 0 && newCol < C && !visited[newId] && Math.abs(heights[newRow][newCol] - heights[row][col]) <= mid) {
                        queue.offer(new int[]{newRow, newCol});
                        visited[newId] = true;
                    }
                }
            }
            // 二分
            if(visited[LEN - 1]) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
}
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

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int R = heights.length;         // 几行
        int C = heights[0].length;      // 几列
        int LEN = R * C;

        int left = 0;
        int right = 999999;
        int res = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            // 每次取到一次mid后，开始BFS >_<
            boolean[] visited = new boolean[LEN];
            visited[0] = true;
            // 二分
            if(DFS(0, 0, heights, R, C, mid, visited)) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }

    private int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    private boolean DFS(int row, int col, int[][] heights, int R, int C, int mid, boolean[] visited) {
        for(int[] direction : directions) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            int newId = newRow * C + newCol;
            if(newRow >= 0 && newRow < R && newCol >= 0 && newCol < C && !visited[newId] && Math.abs(heights[newRow][newCol] - heights[row][col]) <= mid) {
                visited[newId] = true;
                DFS(newRow, newCol, heights, R, C, mid, visited);
            }
        }
        return visited[R * C - 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

>>> 时间复杂度："O(mnlogC)"，其中C为二分区间的上界值10^6
>>> 空间复杂度："O(mn)"
1
2

方法三——Dijkstra

Dijkstra本质是一种启发式搜索算法。归根结底，本题还是一个最短路径问题，只是整条路径的权值不再是各边权值之和，而是各边权值的最大值。另外，本题也没有负数权值的边，完全符合Dijkstra的适用范围。

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int R = heights.length;
        int C = heights[0].length;
        int LEN = R * C;
        int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        int[] dist = new int[LEN];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        boolean[] visited = new boolean[LEN];

        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        queue.offer(new int[]{0, 0, 0});

        while (!queue.isEmpty()) {
        	// 找最短的边
            int[] edge = queue.poll();
            int row = edge[0];
            int col = edge[1];
            int id = row * C + col;
            if(visited[id]) {
                continue;
            }
            if(id == LEN - 1) {
                return dist[LEN - 1];
            }
            visited[id] = true;
            // 更新
            for(int[] direction : directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                int newId = newRow * C + newCol;
                if(newRow >= 0 && newRow < R && newCol >= 0 && newCol < C && Math.max(edge[2], Math.abs(heights[newRow][newCol] - heights[row][col])) < dist[newId]) {
                    dist[newId] = Math.max(edge[2], Math.abs(heights[newRow][newCol] - heights[row][col]));
                    queue.offer(new int[]{newRow, newCol, dist[newId]});
                }
            }
        }
        return dist[LEN - 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

时间复杂度：Dijkstra算法仅与图的边数有关，本题近似看成边数为"mn"，则复杂度为"O(mnlogmn)"
空间复杂度："O(mn)"
1
2

水位上升的泳池

在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i, j) 的平台高度。
现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。你只能在被水淹没的地方游泳。

你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？

注：2 <= N <= 50，grid[i][j] 是 [0, …, N×N - 1] 的排列。

方法一——并查集

假如此时的时间为t，则能知道水刚刚淹没的位置p，p向四周比它低的平台进行连通。时间t递增，当到达某个时间时，左上角与右下角连通，此时的t即为正确答案。

class Solution {
    public int swimInWater(int[][] grid) {
        int R = grid.length;
        int C = grid[0].length;
        int LEN = R * C;

		// 实现时间到位置的直接映射（知道时间t，立即知道此时水刚刚淹没的位置）
        int[] positions = new int[LEN];
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                positions[grid[i][j]] = i * C + j;
            }
        }

		// 递增t，进行连通
        UnionSet unionSet = new UnionSet(LEN);
        int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        for(int t = 0; t < LEN; t++) {
            int position = positions[t];
            int row = position / C;
            int col = position % C;
            for(int[] direction : directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                int newPosition = newRow * C + newCol;
                if(newRow >= 0 && newRow < R && newCol >= 0 && newCol < C && grid[newRow][newCol] < grid[row][col]) {
                    unionSet.union(position, newPosition);
                }
            }
            if(unionSet.isUnion(0, LEN - 1)) {
                return t;
            }
         }
        return 0;
    }
}

/*
 * UnionSet模板略
 */
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

>>> 时间复杂度："O(n2logn2)"
>>> 空间复杂度："O(n2)"
1
2

方法二——二分法+BFS/DFS

我们已知正确答案区间最大值的最小值(0)和最大值(N * N - 1)，二分法呼之欲出。每次取的mid值作为限制条件（小于等于mid的平台可游，大于mid的平台不能游），看看能否从左上角到达右下角(DFS/BFS)。并以此为依据进行二分。

class Solution {
    public int swimInWater(int[][] grid) {
        int R = grid.length;
        int C = grid[0].length;
        int LEN = R * C;

        int left = 0;
        int right = LEN - 1;
        int res = 0;
        int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        while (left <= right) {
            int mid = (left + right) / 2;
            // 每次取一个mid的值，开始BFS
            if(mid < grid[0][0]) {
                left = mid + 1;
                continue;
            }
            boolean[][] visited = new boolean[R][C];
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{0, 0});
            visited[0][0] = true;
            while (!queue.isEmpty()) {
                int[] point = queue.poll();
                int row = point[0];
                int col = point[1];
                for(int[] direction : directions) {
                    int newRow = row + direction[0];
                    int newCol = col + direction[1];
                    if(newRow >= 0 && newRow < R && newCol >= 0 && newCol < C && !visited[newRow][newCol] && grid[newRow][newCol] <= mid) {
                        queue.offer(new int[]{newRow, newCol});
                        visited[newRow][newCol] = true;
                    }
                }
            }
            // 二分
            if(visited[R - 1][C - 1]) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
}
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

class Solution {
    public int swimInWater(int[][] grid) {
        int N = grid.length;
        int left = 0;
        int right = N * N - 1;
        int res = 0;

        while (left <= right) {
            int mid = (left + right) / 2;
            // 每次取一个mid值，开始DFS
            if(mid < grid[0][0]) {
                left = mid + 1;
                continue;
            }
            boolean[][] visited = new boolean[N][N];
            visited[0][0] = true;
            // 二分
            if(DFS(0, 0, grid, visited, mid)) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }

    private int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    private boolean DFS(int row, int col, int[][] grid, boolean[][] visited, int mid) {
        int N = grid.length;
        for(int[] direction : directions) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if(newRow >= 0 && newRow < N && newCol >= 0 && newCol < N && !visited[newRow][newCol] && grid[newRow][newCol] <= mid) {
                visited[newRow][newCol] = true;
                DFS(newRow, newCol, grid, visited, mid);
            }
        }
        return visited[N - 1][N - 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

>>> 时间复杂度："O(n2logn2)"
>>> 空间复杂度："O(n2)"
1
2

方法三——Dijkstra

Dijkstra本质是一种启发式搜索算法。归根结底，本题还是一个最短路径问题，只是整条路径的权值不再是各边权值之和，而是经过的点的最大值（边的全值，置为其所指向的点的值）。另外，本题也没有负数权值的边，完全符合Dijkstra的适用范围。

class Solution {
    public int swimInWater(int[][] grid) {
        int N = grid.length;
        int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        boolean[][] visited = new boolean[N][N];
        int[][] dist = new int[N][N];
        for(int[] arr : dist) {
            Arrays.fill(arr, N * N);
        }
        dist[0][0] = grid[0][0];
        
        Queue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> grid[o[0]][o[1]]));
        queue.offer(new int[]{0, 0});

        while (!queue.isEmpty()) {
            // 找最短的边
            int[] point = queue.poll();
            int row = point[0];
            int col = point[1];
            if(visited[row][col]) {
                continue;
            }
            if(row == N - 1 && col == N - 1) {
                return dist[row][col];
            }
            visited[row][col] = true;
            // 更新
            for(int[] direction : directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                if(newRow >= 0 && newRow < N && newCol >= 0 && newCol < N && Math.max(dist[row][col], grid[newRow][newCol]) < dist[newRow][newCol]) {
                    dist[newRow][newCol] = Math.max(dist[row][col], grid[newRow][newCol]);
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }
        return dist[N - 1][N - 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

>>> 时间复杂度："O(n2logn2)"
>>> 空间复杂度："O(n2)"
1
2

总结：

对于数组（m x n的矩阵），用int[i][j]和int[id]（其中id=i*C+j）都可以唯一表示其位置。虽然表面是一维和二维，但其实空间复杂度都是 $O (m n)$
一般对于DFS，在启动下一个DFS之前，标记visited已访问
一般对于BFS，在入队(offer)时标记visited，而不是在出队(poll)时标记visited
Dijkstra有固定模板，是在出队时标记visited
并查集模板要记牢；并查集的关键在于连通

$E N D$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/695537