刷题笔记6-图论

一、图论基础

1、图的表示

图可以分为：

  • 有向无权图
  • 有向有权图
  • 无向无权图
  • 无向有权图

1.1、邻接表

对于邻接表来说

  • 有向/无向：没有影响，在相应结点的邻居结点表中增减即可

  • 有权/无权：对结构有一定影响。

    有权：List<int[]>[] graph 其中List中的int[]放两个值，一个是结点值，一个是权重

1
2
3
4
5
6
7
List<Integer>[] graph; // int[][] 结构也可

for(int i = 0; i < graph.length; i++){ // 遍历结点
    for(int j = 0; j < graph[i].length; j++){ // 遍历每个结点的邻居结点
        
    }
}

1.2、邻接矩阵

对于临界矩阵来说

  • 有向/无向：遍历矩阵的【右上角】和【全部】的区别
  • 有权/无权：矩阵中的值是0/int和0/1的区别
1
2
3
4
5
6
7
8
int[][] graph; // n*n的矩阵

int n = graph.length;
for(int i = 0; i < n; i++){ // 遍历起始节点
    for(int j = i + 1; j < n; j++){ // 遍历终止结点
        graph[i][j] // 1表示存在从i结点到j结点的路径
    }
}

2、图的遍历

图的遍历一般程度上可以理解为多叉树的遍历，但是需要注意【环的存在】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
boolean visited; // 记录结点是否已经访问过
List<Integer> path; // 记录一条路径

void traversal(Graph graph, int s){
    if(visited[s]){
        return;
    }
    
    visited[s] = true;
    path.add(s);
    
    for(int neighbor : graph.neighbors(s)){
        traversal(graph, neighbor);
    }
    // 回溯
    path.remove(new Integer(s));
}

3、例题

【797. 所有可能的路径】

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
List<List<Integer>> paths;
List<Integer> path;
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    paths = new ArrayList<>();
    path = new ArrayList<>();
    
    traversal(graph, 0, graph.length - 1);
    return paths;
}

private void traversal(int[][] graph, int begin, int end){
    path.add(begin);
    if(begin == end) {
        paths.add(new ArrayList<>(path));
        path.remove(new Integer(begin));
        return;
    }
    for(int i = 0; i < graph[begin].length; i++){
        traversal(graph, graph[begin][i], end);
    }
    path.remove(new Integer(begin));
}

二、拓扑排序

0、图的生成与遍历

给定图的结点数n，以及结点之间的依赖关系dependency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
	n(int) 节点数
	dependency(int[][]) 结点之间依赖关系 dependency[i]是一个[from, to]的二元数组
*/
private List<Integer>[] buildGraph(int n, int[][] dependency){
    List<Integer>[] graph = new List[n];
    for(int i = 0; i < n; i++){
        graph[i] = new ArrayList<>();
    }
    
    for(int[] pair : dependency){
        int from = pair[0];
        int to = pair[1];
        graph[from].add(to);
    }
    
    return graph;
}

1、判断是否存在环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
boolean[] visited;
boolean[] onPath;
boolean isCycle;
private void traversal(int[][] graph, int s){
    if(onPath[s]){
        isCycle = true;
        return;
    }
    if(visited[s]){
        return;
    }
    
    visited[s] = true;
    onPath[s] = true;
    
    for(int neighbor : graph[s]){
        traversal(graph, neighbor);
    }
    
    onPath[s] = false;
}

2、拓扑序列

207. 课程表

如果图G中不存在环，G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。

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
// 改造一下traversal函数
boolean[] visited;
boolean[] onPath;
boolean isCycle;

List<Integer> postOrder;
private void traversal(int[][] graph, int s){
    if(onPath[s]){
        isCycle = true;
        return;
    }
    if(visited[s]){
        return;
    }
    
    onPath[s] = true;
    visited[s] = true;
    
    for(int[] neighbor : graph[s]){
        traversal(graph, s);
    }
    
    onPath[s] = false;
    postOrder.add(s);
}

// 最后再将postOrder逆序得到就是结果

【重点理解：为什么图的后序遍历就是拓扑排序】

如果图中不存在环，那么图就可以看成是一颗多叉树，如图。

image-20221029210620536

那么从结点0开始的后序遍历的序列之一就是[7,9,16,11, | 6,10,8,19,2, | 3,4,5, | 0]

其实就是从最底层到最高层的排列。

它满足了from结点都在to结点的后面（所以最后结果需要逆序，使from结点在前面）

【局部 ==》全局】

而这只是这个图的一部分，可以把这部分抽象成一个结点S，那么同样使用前面的函数，在得到的遍历结果中，图中直接指向或者间接指向S的结点都会在其后面，逆序之后就在前面，所以得出的结果就是正确的。

（同时在细节上visited和onPath数组保证结点只被遍历一次以及不会出现环）

三、二分图

二分图：直观的理解就是能够用两种颜色给一张图上色，使得每条边两端的结点颜色不同

【判断二分图】

思路：一边遍历，一边给图上色

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
boolean[] visited; // 记录结点是否被访问
boolean[] color; // 记录结点的颜色 true 和 false 两种
boolean isBinary = true;

public boolean isBipartite(int[][] graph) {
    int n = graph.length; // 结点数
    visited = new boolean[n];
    color = new boolean[n];
    
    for (int i = 0; i < n; i++){
        if(!visited[i])
        	traversal(graph, i); // 遍历不同的liang
    }
    
    return isBinary;
}

/**
* 这里的 color 被new了之后每一个值都是 false 也就成了默认的颜色，只需要去改变对应结点的颜色即可
* 由于这里的图是无向图，所以traversal一个结点就是遍历这个连通分支
*/
void traversal(int[][] graph, int v){
    if(!isBinary) return;
    
    visited[v] = true;
    for(int w : graph[v]){
        if(!visited[w]){
            color[w] = !color[v];
            traversal(graph, w);
        } else {
            if(color[w] == color[v]){
                isBinary = false;
            }
        }
    }
}

四、Union-Find 算法

1、union-find的算法思想

  • 基本思想：用下标代替实际的结点，parent数组存储父结点，这样就可以较为快速的实现【合并】和【判断是否相连】的操作
  • 进阶思想：无论是 union 操作还是 connected 操作，其复杂度的局限都在于 find 函数，即从一个结点找到根节点的过程，如果这个结点距离结点越近，复杂度越低。而结点与根节点的距离一方面取决于 union 时的插入方式，如果插入不当，就可能形成链式的连通分量，复杂度是最高的，我们希望尽量降低树的高度，可以在 union 中采取 【小树插大树】的方式，使得树的高度尽可能的小。
  • 路径压缩：在 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
51
52
53
public class UnionFind {
    int count; // 连通分量个数
    int[] parent; // 结点的父节点
    int[] size; // 该节点所处连通分量的结点数
    
    public UnionFind(int n){
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++){
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    public void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ){
            return;
        }
        /*
        * 小树插到大树上，保持树的平衡 维持 logN 的时间复杂度
        * */
        if(size[rootP] > size[rootQ]){
            parent[rootQ] = rootP;
        } else {
            parent[rootP] = rootQ;
        }
        size[rootP] += size[rootQ];
        size[rootQ] += size[rootP];
        count--;
    }
    
    public boolean connected(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
    
    private int find(int p){
        if(p >= parent.length) return -1;
        while (parent[p] != p){
            parent[p] = parent[parent[p]]; // 路径压缩 使得所有非根结点都直接连接在根上 使树高维持在2
            p = parent[p];
        }
        return p;
    }
    
    public int count(){
        return count;
    }
}

2、Union-Find算法的应用

2.1、130. 被围绕的区域

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

这道题其实使用DFS算法可以很好地解决，但是也是可以体现Union-Find算法思想的一道题目

加深对于DFS算法的理解

DFS算法是深度优先，在二叉树中体现为从根节点不断地向叶节点前进，在图中是体现为从一个结点不断地向其邻居结点前进。

其实在这道题中，把这个矩阵理解为一副图的话，DFS就显得比较自然了

1、遍历矩阵的四周，如果是'O'，则进入dfs，将所有与其相连的'O'变成特殊符号

2、遍历矩阵，将特殊符号变回'O'，把'O'变成'X'

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
// 使用 DFS 解决
    /*
    x x x x
    x o x o
    x o o x
    o x x o

    [要深入理解 dfs 的内涵]


    边界坐标的特点: [0/m-1][0/n-1]
     */
    int m;
    int n;
    private void dfs(char[][] board){
        m = board.length;
        n = board[0].length;

        // 遍历board的四条边
        int i = 0, j = 0;
        do {
            if(board[i][j] == 'O'){
                dfsHelper(board, i, j);
            }
            int[] next = forward(i,j);
            i = next[0];
            j = next[1];
        } while (i > 0  || j > 0); // ① 考虑到 forward 函数会返回 {-1, -1} 所以要改成 >0

        // 遍历整个board 把 'O' 换成 'X' 把 '#' 换成 'O'
        for (int a = 0; a < m; a++){
            for (int b = 0; b < n; b++){
                if (board[a][b] == 'O') board[a][b] = 'X';
                if (board[a][b] == '#') board[a][b] = 'O';
            }
        }
    }

    /*
    * 这里的 DFS 就有些不同于 树的 DFS
    * DFS: 只处理一个结点，然后用递归向四周扩散深入
    * */
    private void dfsHelper(char[][] board, int x, int y){
        /*
        这里要改成 != 'O' 而不是 == 'X'
        != 'O' 针对的是两种情况 == 'X' 和 == '#'
        == 'X' 肯定是直接 return
        == '#' 的情况，其实也可以return 因为这个 '#' 周围的格子已经被遍历过了 (在其从'O'变成'#'之后)
         */
        if(board[x][y] != 'O') return;
        if(board[x][y] == 'O') board[x][y] = '#';

        if (x > 0) dfsHelper(board, x - 1, y); // 上
        if (x < m - 1) dfsHelper(board, x + 1, y); // 下
        if (y > 0) dfsHelper(board, x, y - 1); // 左
        if (y < n - 1) dfsHelper(board, x, y + 1); // 右
    }

    // 在board的四个边上前进
    private int[] forward(int i , int j){
        if (i == 0 && j < n - 1) return new int[]{i, j + 1}; // 上 向右走
        if (j == n - 1 && i < m - 1) return new int[]{i + 1, j}; // 右 向下走
        if (i == m - 1 && j > 0) return new int[]{i, j - 1}; // 下 向左走
        if (j == 0 && i > 0) return new int[]{i - 1, j}; // 左 向上走
        return new int[]{-1, -1};
    }

这道题也是很好的体现，Union-Find的思想在二位数组（矩阵）中判断连通性的例子

  • 根据题意知道：在矩阵的'O'及与其相连的'O'是属于不被替换的'O'，可以算作一个连通分量。【利用一个dummy结点和它们相连】，为什么再找一个dummy结点呢？方便查找。在后续判断这个'O'是否需要被替换时，只需要判断是否和这个dummy结点连通即可。
  • 遍历完四周之后，再次遍历即可完成替换。
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
// 使用 union-find 解决
private void uf(char[][] board){
    int m = board.length;
    int n = board[0].length;
    
    // 最后一个dummy作为 不被 'X' 替换的'O' 的联通分量中的一个结点 来寻找该连通分量中的其他结点
    UnionFind uf = new UnionFind(n*m+1);
    
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            
            int val = i * n + j; // 二维数组转化为一维
            
            // 将矩阵四周的'O'和dummy连通
            if( (i == 0 || i == m - 1 || j == 0 || j == n - 1) &&
                        board[i][j] == 'O' ){
                uf.union(val, n*m);
            } else if (board[i][j] == 'O'){
                // 上
                if(i > 0 && board[i-1][j] == 'O') uf.union((i-1)*n+j, val);
                // 下
                if (i < m - 1 && board[i+1][j] == 'O') uf.union((i+1)*n+j, val);
                // 左
                if (j > 0 && board[i][j-1] == 'O') uf.union(i*n+(j-1), val);
                // 右
                if (j < n - 1 && board[i][j+1] == 'O') uf.union(i*n+(j+1), val);
                /* 
                // 如果不在能够连通分量中 则改成 X
                if (!uf.connected(val, n*m)){
                    board[i][j] = 'X';
                }
                 */
            }
        }
    }
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if(board[i][j] == 'O' && !uf.connected(i*n+j, n*m)){
                board[i][j] = 'X';
            }
        }
    }
}

2.2、990. 等式方程的可满足性

这道题就是典型需要利用Union-Find解决。相等和不相等就相当于连通和不连通，核心就是 union 和 判断是否 connected

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean equationsPossible(String[] equations) {
    UnionFind uf = new UnionFind(26);
    for (String equation : equations) {
        if(equation.charAt(1) == '!') continue;
        char c1 = equation.charAt(0);
        char c2 = equation.charAt(3);
        uf.union(c1-'a', c2-'a');
    }
    for (String equation : equations) {
        if (equation.charAt(1) == '=') continue;
        char c1 = equation.charAt(0);
        char c2 = equation.charAt(3);
        if(uf.connected(c1-'a', c2-'a')) return false;
    }
    return true;
}

五、最小生成树算法

Kruskal算法

  1. 对所有边进行排序
  2. 从权重最小的边开始，依次将边加入到结点集中
  3. 检查是否产生环（并查集），如果有就剔除

1584. 连接所有点的最小费用

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

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

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

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
/**
 * Kruskal 最小生成树算法
 * 1584. 连接所有点的最小费用
 * https://leetcode.cn/problems/min-cost-to-connect-all-points/
 */
int[] parent;
int[] size;
public int minCostConnectPoints(int[][] points) {
    int n = points.length; // 节点个数
    List<int[]> edges = new ArrayList<>();
    for (int i = 0; i < n; i ++){
        for (int j = i + 1; j < n; j++){
            int cost = Math.abs(points[i][0] - points[j][0]) +
                               Math.abs(points[i][1] - points[j][1]);
            edges.add(new int[]{i, j, cost});
        }
    }
    edges.sort(Comparator.comparingInt(a -> a[2])); // 升序排列
    
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    
    int sum = 0;
    for (int[] edge : edges) {
        if(union(edge[0], edge[1])){
            sum += edge[2];
        }
    }
    return sum;
}

boolean union(int v, int w) {
    while (parent[v] != v) {
        parent[v] = parent[parent[v]];
        v = parent[v];
    }
    while (parent[w] != w) {
        parent[w] = parent[parent[w]];
        w = parent[w];
    }
    if (w == v) {
        return false; // 处在一个连通分量中
    } else {
        if (size[w] > size[v]) {
            parent[v] = w;
            size[w] += size[v];
        } else {
            parent[w] = v;
            size[v] += size[w];
        }
        return true;
    }
}

六、Dijstra算法

1、框架

  1. 建图：将题目中对应的图模型建立起来（以邻接表的形式）
  2. 封装每个图节点 Node：节点id 和 "代价"(从 start 节点到当前节点的最值)
  3. 使用一个 cost 数组：cost[i] 记录从 start 节点开始到 i 节点的 "代价" 最值
  4. 使用 优先队列 queue：目的是每次能够取出最小（最大）的节点，加速 BFS
  5. 从 start 节点开始 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
38
int[] dijstra(..args){
    // 建图
    List<int[]>[] graph = buildGraph();
    
    // start节点到相应节点的"代价"最值
    int[] costTo = new int[n];
    initialize the array;
    costTo[start] = init_value;
    
    // 使用优先级队列，对所有封装起来的图节点按照"cost"排序
    Queue<Node> queue = new PriorityQueue<>();
    queue.offer(new a start node);
    
    while(!queue.isEmpty()){
        Node node = queue.poll();
        int id = node.id;
        int cost = node.costFromStart;
        
        if(cost > costTo[id]){ // 已经有更优的
            continue;
        }
        
        for(int[] next : graph[id]){
            int nextId = next[0];
            // 这个地方可以衍生出很多的变式，对于代价是相加，对于概率是相乘，也有可能是求最大值
            int nextCost = func(next[1], costTo[id]);
            
            if(nextCost < costTo(nextId)){
                // 更新
                costTo[nextId] = nextCost;
                queue.offer(new this node);
            }
            
        }
    }
    
    return costTo;
}
leetcode刷题笔记
#leetcode
刷题笔记6-图论
http://example.com/2022/10/15/leetcode/刷题笔记6（图论）/
作者
zhc
发布于
2022年10月15日
许可协议