图论-拓扑排序

发表于 更新于 分类于 Artalk： loading...

拓扑排序针对的是有向无环图DAG，属于图的广度优先搜索的应用

DAG一定存在拓扑序列

关于拓扑排序，参见维基百科；这篇知乎文章–《图文详解拓扑排序》写得也很棒，留作参考

相关知识已经很熟悉，这里不再赘述

“对于DAG中顶点的一种排列，使得对于每个有向边 i→ji\to j ， ii 都在 jj 之前”

大致思想

每一轮，找当前入度为0的顶点，然后将这些顶点依次入队(并从图中删去，更新入度）

在 BFS\text{BFS} 的基础上维护一个 d[]d[] 数组保存每个顶点的入度

伪代码

image-20220410183640431

首先，一个DAG，一定至少存在一个入度为0的点

反证法：

假设这个无环图有 nn 个顶点，且每一个点入度都不为0，则可以顺着起始点 <prev→orig><prev\to orig>，找到其前一个顶点 prevprev ，且总能找到。直到找到第 n+1n + 1 个顶点，根据抽屉原理，一定存在两个相同的点，则存在环，与条件不符。

删去这个点和其出边，将入度为0的出边另一端点入队

新一轮开始，继续找入度为0的点

直至队列为空

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
boolean topsort() {
    // 这里使用数组模拟队列
    int hh = 0, tt = -1; // 注意初始化时 tt = -1
    for (int i = 1; i <= n; ++i) {
        if (d[i] == 0) q[++tt] = i; // 遍历整个图，将入度为0的点入队
    }
    while (hh <= tt) {
        int cur = q[hh++];
        for (int i = h[cur]; i != -1; i = ne[i]) {
            int j = e[i]; // 找cur的所有出边
            d[j]--; // 删去边 i->j 则j的入度减1 
            if (d[j] == 0) q[++tt] = j; // 如果入度为0，则入队
        }
    }
    return tt == 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;
import java.io.*;

class Main{
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int N = 100010, M = N * 2;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static boolean[] st = new boolean[N];
    static int idx = 0;
    static int[] d = new int[N];
    static int[] q = new int[N];
    static int n;
    public static void main(String[] args) throws Exception {
        idx = 0;
        Arrays.fill(h, -1);
        String[] strs = cin.readLine().split(" ");
        n = Integer.parseInt(strs[0]);
        int m = Integer.parseInt(strs[1]);
        int a, b;
        for (int i = 0; i < m; ++i) {
            String[] tmp = cin.readLine().split(" ");
            a = Integer.parseInt(tmp[0]); b = Integer.parseInt(tmp[1]);
            add(a, b);
            d[b]++; // a->b 则b的入度加1
        }
        if (topsort()) {
            for (int i = 0; i < n; ++i) log.write(q[i] + " ");
        } else log.write("-1");
        
        log.flush();
        log.close();
        cin.close();
    }
    static boolean topsort() throws Exception {
        int hh = 0, tt = -1; // 注意初始化时 tt = -1
        for (int i = 1; i <= n; ++i) {
            if (d[i] == 0) q[++tt] = i; // 遍历整个图，将入度为0的点入队
        }
        while (hh <= tt) {
            int cur = q[hh++];
            for (int i = h[cur]; i != -1; i = ne[i]) {
                int j = e[i]; // 找cur的所有出边
                d[j]--; // 删去边 i->j 则j的入度减1 
                if (d[j] == 0) q[++tt] = j; // 如果入度为0，则入队
            }
        }
        return tt == n - 1; // 判断是否所有的顶点都进队了，否则就是有环的
    }

    static void add(int u, int val) {
        e[idx] = val;
        ne[idx] = h[u];
        h[u] = idx++;
    }
    
}

拓扑排序常用来确定具有依赖关系的AOV网络中，活动发生的顺序

例如，1462. 课程表 IV，来确定课程之间的先修关系

完整代码

问题描述

image-20221027222916114

代码

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
class Solution {
    public static final int N = 110, M = 10010;
    public static int[] e = new int[M];
    public static int[] h = new int[N];
    public static int[] ne = new int[M];
    public static int idx;
    public static int[] inDegree = new int[N];
    public void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) {
        // 尝试用拓扑排序的思路去做
        Arrays.fill(h, -1);
        this.idx = 0;
        Arrays.fill(inDegree, 0);
        for (int[] tt : prerequisites) {
            int a = tt[0], b = tt[1];
            add(a, b);
            inDegree[b]++;
        }
        Queue<Integer> q = new ArrayDeque<>();
        // 先将入度为0的顶点入队
        for (int i = 0; i < n; ++i) {
            if (inDegree[i] == 0) q.offer(i);
        }
        List<Boolean> res = new ArrayList<>();
        List<Set<Integer>> pre = new ArrayList<>();
        for (int i = 0; i < n; ++i) pre.add(new HashSet<>());
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int i = h[cur]; i != -1; i = ne[i]) {
                int next = e[i];
                // 添加前驱信息
                Set<Integer> tt = pre.get(next);
                for (Integer x : pre.get(cur)) tt.add(x);
                tt.add(cur);
                // 相邻节点入度减1
                inDegree[next]--;
                if (inDegree[next] == 0) q.offer(next);
            }
        }
        // 判断b的前驱节点中是否有a
        for (int[] query : queries) {
            int a = query[0], b = query[1];
            if (pre.get(b).contains(a)) res.add(true);
            else res.add(false);
        }
        return res;
    }
}

本题也可以用Floyd算法来解决，构建图后，转为「求多源最短路径问题」

如果a到b的距离为无穷大，则a不是b的先修课程