图

发表于 更新于 分类于 阅读次数： 本文字数： 7k 阅读时长 ≈ 25 分钟

1. 图的基本应用

1.1 找到小镇的法官

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

  1. 小镇法官不会信任任何人。
  2. 每个人（除了小镇法官）都信任这位小镇法官。
  3. 只有一个人同时满足属性 1 和属性 2 。

给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

思路

在有向图中，一个节点的入度是指向该节点的边的数量；而一个节点的出度是从该节点出发的边的数量。

ai->bi相当于一条边，从ai指向bi，那么ai的出度加一，bi的入度加一，那么小镇法官应满足：

  • 入度为n-1(即所有人都信任法官)
  • 出度为0(即法官不信任任何人)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] indegree=new int[n+1];
        int[] outdegree=new int[n+1];
        // 出度、入度统计
        for(int[] edge:trust){
            ++outdegree[edge[0]];
            ++indegree[edge[1]];
        }
        for(int i=1;i<=n;i++){
            // 判断是否为法官
            if(outdegree[i]==0&&indegree[i]==n-1){
                return i;
            }
        }
        return -1;
    }
}

1.2 最大网络秩

n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。

两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市 直接 相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算 一次 。

整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。

给你整数 n 和数组 roads，返回整个基础设施网络的 最大网络秩 。

思路

在有向图中，每个点的度数等于其入度与出度之和；在无向图中，每个点的度数等于与其相连的边的数量。

直观思路：暴力枚举每个城市的度数，然后依次选取两个城市进行比较得出最大网络秩，满足条件为：

  • 若两个城市之间有道路相连，那么它们的网络秩为degree[i]+degree[j]-1
  • 若两个城市之间没有道路相连，那么它们的网络秩为degree[i]+degree[j]

依次比较得出最大值即可。

贪心思路：要求最大网络秩，只需要考虑度数最大以及度数次大的城市即可。

不妨设度数最大值为first，度数次大值为second，图中可能存在多个城市度数值等于first或second，那么我们设所有度数值等于最大值的城市构成一个集合firstAttr，所有度数值等于次大值的城市构成一个集合secondAttr，接下来求最大网络秩，我们只需在这两个集合内考虑即可，分为以下几种情况讨论：

  • 若firstAttr.size()==1，考虑到first>=second+1 -> first+second-1>=second+second，即在secondAttr中选取两个城市组成的网络秩大小不可能超过在这两个集合中分别选取一个，那么我们必须选取firstAttr中的唯一城市，然后在secondAttr中依次枚举，寻找是否有不与该城市直接相连的城市，若有，则返回first+second；否则返回first+second-1；
  • 若firstAttr.size()>1，考虑到first>=second+1 -> first+first-1>=first+second>second+second，即在firstAttr集合中选择两个城市组成的网络秩最大，设m为城市道路总数，考虑；
    • 若firstAttr.size()*(firstAttr.size()-1)/2>m，即任意选择两个城市组成的道路总数大于现有道路总数，说明此时一定存在两个城市，它们之间没有道路相连，最大网络秩为first+first；
    • 反之，则枚举集合中的城市，依次选择两个城市，判断是否有道路相连，若无，则返回first+first；否则返回first+first-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
class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        boolean[][] connect=new boolean[n][n];
        int[] degree=new int[n];
        for(int[] road:roads){
            int x=road[0],y=road[1];
            degree[x]++;
            degree[y]++;
            connect[x][y]=true;
            connect[y][x]=true;
        }
        int first=-1,second=-2;
        List<Integer> firstAttr=new ArrayList<>();
        List<Integer> secondAttr=new ArrayList<>();
        for(int i=0;i<n;i++){
            if(degree[i]>first){// 若度数大于first，更新first
                second=first;// first自然变为了second
                secondAttr=new ArrayList(firstAttr);// 更新secondAttr
                firstAttr.clear();
                firstAttr.add(i);
                first=degree[i];
            }else if(degree[i]==first){
                firstAttr.add(i);
            }else if(degree[i]>second){// 更新second
                secondAttr.clear();
                secondAttr.add(i);
                second=degree[i];
            }else if(degree[i]==second){
                secondAttr.add(i);
            }
        }
        if(firstAttr.size()==1){// firstAttr仅有一个城市，必须选择
            int u=firstAttr.get(0);
            // 枚举
            for(int v:secondAttr){
                if(!connect[u][v]){
                    return first+second;
                }
            }
            return first+second-1;
        }else{
            int m=roads.length;
            if(firstAttr.size()*(firstAttr.size()-1)/2>m){// 判断是否一定存在两个城市不相连
                return first*2;
            }else{// 枚举
                for(int u:firstAttr){
                    for(int v:firstAttr){
                        if(u!=v&&!connect[u][v]){
                            return first*2;
                        }
                    }
                }
                return first*2-1;
            }
        }
    }
}

2. 图遍历及其应用

2.1 岛屿数量

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

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

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

思路

深度优先搜索或广度优先搜索，每次遇到'1'则从该点出发遍历图，将'1'置为'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
class Solution {
    public int numIslands(char[][] grid) {
        int n=grid.length,m=grid[0].length;
        int num=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]=='1'){
                    num+=dfs(grid,i,j);
                }
            }
        }
        return num;
    }
    public int dfs(char[][] grid,int cur_x,int cur_y){
        // 判断是否越界
        if(cur_x<0||cur_y<0||cur_x>=grid.length||cur_y>=grid[0].length||grid[cur_x][cur_y]!='1'){
            return 0;
        }
        grid[cur_x][cur_y]='0';
        int ans=1;
        int[] dx=new int[]{-1,0,1,0};
        int[] dy=new int[]{0,1,0,-1};
        // 四个方向遍历
        for(int i=0;i<4;i++){
            int x=cur_x+dx[i],y=cur_y+dy[i];
            dfs(grid,x,y);
        }
        return ans;
    }
}

2.2 判断二分图

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

  • 不存在自环（graph[u] 不包含 u）。
  • 不存在平行边（graph[u] 不包含重复值）。
  • 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
  • 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

如果图是二分图，返回 true ；否则，返回 false 。

思路

采用三色标记法，对当前节点进行颜色标记，然后以从该节点开始遍历图，若相邻节点未被标记，那么将其标记上不同的颜色；若相邻节点已被标记，判断其颜色是否和当前节点颜色相同，若相同，返回false；若不同，则继续遍历。

代码

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
class Solution {
    public boolean isBipartite(int[][] graph) {
        int n=graph.length;
        int[] color=new int[n];
        for(int i=0;i<n;i++){
            // 判断当前节点是否被标记及合理性
            if(color[i]==0&&!dfs(graph,i,1,color)){
                return false;
            }
        }
        return true;
    }
    public boolean dfs(int[][] graph,int u,int c_color,int[] color){
        color[u]=c_color;
        for(int ed:graph[u]){
            // 相邻节点颜色相同，返回false
            if(color[ed]==color[u]){
                return false;
            }
            // 未被标记，递归遍历
            if(color[ed]==0&&!dfs(graph,ed,3^c_color,color)){
                return false;
            }
        }
        return true;
    }
}

2.3 被围绕的区域

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

思路

从边界开始遍历，若遇到'O'则将其置为'1'，并从该节点开始遍历图。

这样处理后，所有与边界相接的'O'均变为了'1'，而对于图中的其它'O'，由于其未与边界相接，即都被'X'包围，将其置为'X'即可，对于'1'，则将其还原为'O'。

代码

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
class Solution {
    public void solve(char[][] board) {
        int n=board.length,m=board[0].length;
        // 边界处理
        for(int i=0;i<n;i++){
            dfs(board,i,0);
            dfs(board,i,m-1);
        }
        for(int j=0;j<m;j++){
            dfs(board,0,j);
            dfs(board,n-1,j);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                // 还原变换
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }else if(board[i][j]=='1'){
                    board[i][j]='O';
                }
            }
        }
    }
    // 遍历图
    public void dfs(char[][] board,int x,int y){
        if(x<0||y<0||x>=board.length||y>=board[0].length||board[x][y]!='O'){
            return;
        }
        board[x][y]='1';
        dfs(board,x+1,y);
        dfs(board,x,y+1);
        dfs(board,x-1,y);
        dfs(board,x,y-1);
    }
}

2.4 二进制矩阵中的最短路径

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

  • 路径途经的所有单元格都的值都是 0 。
  • 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度 是该路径途经的单元格总数。

思路

广度优先搜索，每次遍历一层，直到到达右下角。

代码

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 {
    public int shortestPathBinaryMatrix(int[][] grid) {
        // 8个方向
        int[] dx=new int[]{0,1,0,-1,1,1,-1,-1};
        int[] dy=new int[]{1,0,-1,0,1,-1,1,-1};
        int n=grid.length;
        // 判断左上角与右下角是否为1
        if(grid[0][0]==1||grid[n-1][n-1]==1){
            return -1;
        }
        Deque<int[]> hep=new LinkedList<>();
        hep.offer(new int[]{0,0});
        int step=0;
        while(!hep.isEmpty()){
            int s=hep.size();
            step++;
            for(int i=0;i<s;i++){
                int[] p=hep.poll();
                // 若到达右下角，返回路径长度
                if(p[0]==n-1&&p[1]==n-1) return step;
                // 遍历
                for(int j=0;j<8;j++){
                    int x=dx[j]+p[0],y=dy[j]+p[1];
                    if(x<0||y<0||x>=n||y>=n||grid[x][y]==1){
                        continue;
                    }
                    grid[x][y]=1;
                    hep.offer(new int[]{x,y});
                }
            }
        }
        return -1;
    }
}

2.5 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

思路

广度优先搜索，首先将所有腐烂的橘子入队，然后进行广度优先搜索，最后判断新鲜橘子个数是否为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
class Solution {
    public int orangesRotting(int[][] grid) {
        // 四个方向
        int[] dx=new int[]{0,1,0,-1};
        int[] dy=new int[]{1,0,-1,0};
        int n=grid.length,m=grid[0].length;
        // 新鲜橘子个数
        int fr=0;
        Deque<int[]> hep=new LinkedList<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==2){// 腐烂橘子入队
                    hep.offer(new int[]{i,j});
                }else if(grid[i][j]==1){// 新鲜橘子个数加一
                    fr++;
                }
            }
        }
        // 若无新鲜橘子，返回0
        if(fr==0){
            return 0;
        }
        // 扩散时间
        int minutes=-1;
        while(!hep.isEmpty()){
            int s=hep.size();
            for(int i=0;i<s;i++){
                int[] p=hep.poll();
                // 广度优先搜索
                for(int j=0;j<4;j++){
                    int x=p[0]+dx[j],y=p[1]+dy[j];
                    if(x<0||y<0||x>=n||y>=m||grid[x][y]!=1){
                        continue;
                    }
                    // 新鲜橘子腐烂，个数减一
                    fr--;
                    grid[x][y]=2;
                    hep.offer(new int[]{x,y});
                }
            }
            minutes++;
        }
        // 判断是否还有剩余的新鲜橘子
        // 若有，返回-1；反之返回minutes
        return fr==0?minutes:-1;
    }
}

2.6 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

思路

动态规划，当前位置到最近0的距离即为从左、上或右、下位置到最近0的距离加一，状态转移方程：

dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i+1][j],dp[i][j+1])

初始化，若当前位置为0，那么其距离即为0，若当前位置为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
class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int n=mat.length,m=mat[0].length;
        int[][] dp=new int[n][m];
        // 初始化较大数
        final int INF = 1000000;
        for(int i=0;i<n;i++){
            Arrays.fill(dp[i],INF);
        }
        // 若为0，则置0
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mat[i][j]==0){
                    dp[i][j]=0;
                }
            }
        }
        // 从左、上方进行状态转移
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mat[i][j]==0){
                    continue;
                }
                if(i-1>=0){
                    dp[i][j]=Math.min(dp[i][j],dp[i-1][j]+1);
                }
                if(j-1>=0){
                    dp[i][j]=Math.min(dp[i][j],dp[i][j-1]+1);
                }
            }
        }
        // 从右、下方进行状态转移
        for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(mat[i][j]==0){
                    continue;
                }
                if(i+1<n){
                    dp[i][j]=Math.min(dp[i][j],dp[i+1][j]+1);
                }
                if(j+1<m){
                    dp[i][j]=Math.min(dp[i][j],dp[i][j+1]+1);
                }
            }
        }
        return dp;
    }
}

2.7 最短的桥

给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。

岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。

你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。

返回必须翻转的 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
50
51
class Solution {
    private Deque<int[]> cnt=new LinkedList<>();
    private int[] dx=new int[]{0,1,0,-1};
    private int[] dy=new int[]{1,0,-1,0};
    public int shortestBridge(int[][] grid) {
        int n=grid.length;
        int num=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    dfs(grid,i,j);
                    // 广度优先搜索
                    while(!cnt.isEmpty()){
                        int sz=cnt.size();
                        for(int k=0;k<sz;k++){
                            int[] p=cnt.poll();
                            for(int h=0;h<4;h++){
                                int x=p[0]+dx[h],y=p[1]+dy[h];
                                // 判断是否越界
                                if(x<0||y<0||x>=n||y>=n){
                                    continue;
                                }
                                if(grid[x][y]==0){// 为0则加入队列
                                    cnt.offer(new int[]{x,y});
                                    grid[x][y]=-1;
                                }else if(grid[x][y]==1){// 为1说明已经找到了另一座岛，返回num
                                    return num;
                                }
                            }
                        }
                        // 翻转0的数目加一
                        num++;
                    }
                }
            }
        }
        return -1;
    }
    // 深度优先搜索
    public void dfs(int[][] grid,int x,int y){
        if(x<0||y<0||x>=grid.length||y>=grid[0].length||grid[x][y]!=1){
            return;
        }
        grid[x][y]=0;
        cnt.offer(new int[]{x,y});
        dfs(grid,x+1,y);
        dfs(grid,x,y+1);
        dfs(grid,x-1,y);
        dfs(grid,x,y-1);
    }
}

2.8 所有可能的路径

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

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

思路

深度优先搜索+回溯，考虑当前节点，将其加入后，进行深度优先搜索继续遍历，若最终未到达节点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
class Solution {
    List<List<Integer>> cnt=new ArrayList<>();
    List<Integer> tmp=new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // 先将0加入数组tmp中
        tmp.add(0);
        dfs(graph,0);
        return cnt;
    }
    public void dfs(int[][] graph,int v){
        // 若v==graph.length-1，则将tmp加入目标数组中
        if(v==graph.length-1){
            cnt.add(new ArrayList<>(tmp));
            return;
        }
        for(int u:graph[v]){
            // 加入节点
            tmp.add(u);
            // 递归
            dfs(graph,u);
            // 回溯
            tmp.remove(tmp.size()-1);
        }
    }
}

3. 最小生成树

3.1 连接所有点的最小费用

给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

思路

Prim 算法或 Kruskal 算法。

算法：https://oi-wiki.org/graph/mst/

代码

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
class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n=points.length;
        List<int[]>[] graph=new List[n];
        for(int i=0;i<n;i++){
            graph[i]=new ArrayList<>();
        }
        // 求出所有边
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int x1=points[i][0],y1=points[i][1];
                int x2=points[j][0],y2=points[j][1];
                int weight=Math.abs(x1-x2)+Math.abs(y1-y2);
                graph[i].add(new int[]{i,j,weight});
                graph[j].add(new int[]{j,i,weight});
            }
        }
        PriorityQueue<int[]> cnt=new PriorityQueue<>((a,b) -> (a[2]-b[2]));
        boolean[] vis=new boolean[n];
        // 将第0个点的边加入优先队列
        for(int[] ed:graph[0]){
            // 若节点已经添加过，则continue
            if(vis[ed[1]]){
                continue;
            }
            cnt.add(ed);
        }
        // 标记节点已被添加
        vis[0]=true;
        int ans=0;
        while(!cnt.isEmpty()){
            int[] p=cnt.poll();
            int to=p[1];
            int weight=p[2];
            // 若节点被添加过，continue
            if(vis[to]){
                continue;
            }
            // 添加当前节点，并更新最小代价
            for(int[] ed:graph[to]){
                if(vis[ed[1]]){
                    continue;
                }
                cnt.add(ed);
            }
            vis[to]=true;
            ans+=weight;
        }
        return ans;
    }
}

3.2 冗余连接

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

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

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

思路

并查集，初始时，每个节点都属于不同的集合，依次遍历边集，更新节点所属集合，若发现两个节点属于同一集合，则说明改边是多余边。

代码

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
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n=edges.length;
        int[] parent=new int[n+1];
        // 并查集初始化
        for(int i=1;i<=n;i++){
            parent[i]=i;
        }
        // 遍历边集
        for(int[] edge:edges){
            int x=edge[0],y=edge[1];
            // 若两者属于不同集合，合并
            if(find(parent,x)!=find(parent,y)){
                union(parent,x,y);
            }else{// 若两者属于同一集合，说明该边多余
                return edge;
            }
        }
        return new int[0];
    }
    // 寻找根节点
    public int find(int[] parent,int x){
        if(x!=parent[x]) parent[x]=find(parent,parent[x]);
        return parent[x];
    }
    // 合并集合
    public void union(int[] parent,int x,int y){
        parent[find(parent,y)]=parent[find(parent,x)];
    }
}

3.3 最小体力消耗路径

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

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

思路

Dijkstra 算法。

代码

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
class Solution {
    public int minimumEffortPath(int[][] heights) {
        int n=heights.length;
        int m=heights[0].length;
        int[] dx=new int[]{0,1,0,-1};
        int[] dy=new int[]{1,0,-1,0};
        PriorityQueue<int[]> cnt=new PriorityQueue<>((a,b) -> (a[2]-b[2]));
        boolean[] vis=new boolean[n*m];
        int[] dist=new int[n*m];
        cnt.add(new int[]{0,0,0});
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[0]=0;
        while(!cnt.isEmpty()){
            int[] p=cnt.poll();
            int x=p[0],y=p[1],w=p[2];
            int pos=x*m+y;
            if(vis[pos]){
                continue;
            }
            if(x==n-1&&y==m-1){
                break;
            }
            vis[pos]=true;
            for(int i=0;i<4;i++){
                int nx=x+dx[i],ny=y+dy[i];
                // 更新路径长度
                if(nx>=0&&nx<n&&ny>=0&&ny<m&&Math.max(w,Math.abs(heights[nx][ny]-heights[x][y]))<dist[nx*m+ny]){
                    dist[nx*m+ny]=Math.max(w,Math.abs(heights[nx][ny]-heights[x][y]));
                    cnt.add(new int[]{nx,ny,dist[nx*m+ny]});
                }
            }
        }
        return dist[n*m-1];
    }
}

4. 最短路径

4.1 网络延迟时间

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

思路

Dijkstra 算法求出到达所有节点的最短路径，最后比较各个节点的路径长度取最大值得出时间。

代码

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 {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] dist=new int[n+1];
        final int INF = 1000000;
        // dist初始化
        Arrays.fill(dist,INF);
        dist[k]=0;
        int ans=0;
        boolean[] vis=new boolean[n+1];
        PriorityQueue<int[]> hep=new PriorityQueue<>((a,b) -> a[2]-b[2]);
        // 存储图消息
        List<int[]>[] graph=new List[n+1];
        for(int i=1;i<=n;i++){
            graph[i]=new ArrayList<>();
        }
        for(int[] time:times){
            graph[time[0]].add(new int[]{time[1],time[2]});
        }
        hep.add(new int[]{0,k,0});
        while(!hep.isEmpty()){
            int[] p=hep.poll();
            int v=p[1],w=p[2];
            if(vis[v]){
                continue;
            }
            vis[v]=true;
            for(int[] edge:graph[v]){
                // 更新路径长度
                if(w+edge[1]<dist[edge[0]]){
                    dist[edge[0]]=w+edge[1];
                    hep.add(new int[]{v,edge[0],dist[edge[0]]});
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(dist[i]==INF) return -1;
            ans=Math.max(ans,dist[i]);
        }
        return ans;
    }
}

4.2 阈值距离内邻居最少的城市

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

思路

Floyd 算法。

代码

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
class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] dp=new int[n][n];
        // 初始化dp为最大值
        for(int i=0;i<n;i++){
            Arrays.fill(dp[i],Integer.MAX_VALUE);
            // 自身距离为0
            dp[i][i]=0;
        }
        // 根据边初始化dp
        for(int[] edge:edges){
            dp[edge[0]][edge[1]]=edge[2];
            dp[edge[1]][edge[0]]=edge[2];
        }
        // Floyd算法
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(dp[i][k]!=Integer.MAX_VALUE&&dp[k][j]!=Integer.MAX_VALUE)
                    dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k][j]);
                }
            }
        }
        // 求阈值距离内邻居最少的城市
        int index=-1,count=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            int num=0;
            for(int j=0;j<n;j++){
                if(dp[i][j]<=distanceThreshold){
                    num++;
                }
            }
            if(num<=count){
                count=num;
                index=i;
            }
        }
        return index;
    }
}

5. 拓扑排序

5.1 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

思路

题意即判断所给是否为有向无环图，通过深度优先搜索判断图中是否有环即可。

代码

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
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph=new List[numCourses];
        // 构建图
        for(int i=0;i<numCourses;i++){
            graph[i]=new ArrayList<>();
        }
        for(int[] prerequisity:prerequisites){
            graph[prerequisity[1]].add(prerequisity[0]);
        }
        int[] vis=new int[numCourses];
        for(int i=0;i<numCourses;i++){
            // 判断是否有环
            if(vis[i]==0&&!dfs(graph,i,vis)){
                return false;
            }
        }
        return true;
    }
    public boolean dfs(List<Integer>[] graph,int u,int[] vis){
        // 1表示搜索中
        vis[u]=1;
        for(int v:graph[u]){
            // 若未被搜索，则搜索该节点
            if(vis[v]==0){
                boolean flag=dfs(graph,v,vis);
                // 若出现环，返回false
                if(!flag){
                    return false;
                }
            }else if(vis[v]==1){
                return false;
            }
        }
        // 2表示搜索结束
        vis[u]=2;
        return true;
    }
}

5.2 课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

  • 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

思路

广度优先搜索+拓扑排序，首先构造图，将入度为 0 的节点加入队列中（入度为 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
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Deque<Integer> dq=new LinkedList<>();
        int[] result=new int[numCourses];
        int[] indegree=new int[numCourses];
        List<Integer>[] graph=new List[numCourses];
        // 构造图
        for(int i=0;i<numCourses;i++){
            graph[i]=new ArrayList<>();
        }
        for(int[] pq:prerequisites){
            graph[pq[1]].add(pq[0]);
            indegree[pq[0]]++;
        }
        for(int i=0;i<numCourses;i++){
            // 入度为0，入队
            if(indegree[i]==0){
                dq.offer(i);
            }
        }
        int index=0;
        while(!dq.isEmpty()){
            int u=dq.poll();
            result[index++]=u;
            // 更新节点入度
            for(int v:graph[u]){
                --indegree[v];
                // 入度为0，入队
                if(indegree[v]==0){
                    dq.offer(v);
                }
            }
        }
        // 判断index?=numCourses
        // 不等返回空数组
        // 相等返回result
        return index==numCourses?result:new int[0];
    }
}

5.3 课程表 IV

你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [ai, bi] 你 必须 先选 ai 课程。

  • 有的课会有直接的先修课程，比如如果想上课程 1 ，你必须先上课程 0 ，那么会以 [0,1] 数对的形式给出先修课程数对。

先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。

你也得到一个数组 queries ，其中 queries[j] = [uj, vj]。对于第 j 个查询，您应该回答课程 uj 是否是课程 vj 的先决条件。

返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。

思路

拓扑排序，同题解二，每次更新节点入度时，同时更新节点的先决条件。

先决条件用Set存储可以保证去重。

代码

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 {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        // 图
        List<Integer>[] graph=new List[numCourses];
        // 先决条件
        Set<Integer>[] pre=new Set[numCourses];
        // 入度
        int[] degree=new int[numCourses];
        // 初始化
        for(int i=0;i<numCourses;i++){
            graph[i]=new ArrayList<>();
            pre[i]=new HashSet<>();
        }
        // 构造图
        for(int[] pq:prerequisites){
            graph[pq[0]].add(pq[1]);
            // 入度加一
            degree[pq[1]]++;
        }
        Deque<Integer> dq=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(degree[i]==0){
                dq.offer(i);
            }
        }
        // 拓扑排序
        while(!dq.isEmpty()){
            int u=dq.poll();
            for(int v:graph[u]){
                // 入度减一
                degree[v]--;
                // v节点的直接先决条件是u，加入u
                pre[v].add(u);
                // v节点的间接先决条件是u的先决条件
                for(int e:pre[u]){
                    pre[v].add(e);
                }
                if(degree[v]==0){
                    dq.offer(v);
                }
            }
        }
        // 查询query
        List<Boolean> cnt=new ArrayList<>();
        for(int[] query:queries){
            if(pre[query[1]].contains(query[0])){
                cnt.add(true);
            }else{
                cnt.add(false);
            }
        }
        return cnt;
    }
}