java---图的BFS广度优先遍历---拓扑序列（每日一道算法2022.8.25）

题目
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列

涉及数组模拟单链表和队列
可以看我之前的文章：
java 数组模拟队列
java 数组模拟单链表

输入：
3 3
1 2
2 3
1 3
1
2
3
4
5

输出：
1 2 3
1
2

public class BFS_拓扑排序 {
    //初始化，n和m记得定义在外面，h存所有链表的头节点，e存节点值，ne存节点指向
    //q数组模拟队列，d数组存储节点的“入度”
    public static int N = 100010, index = 0, n, m;
    public static int[] h = new int[N], e = new int[N], ne = new int[N];
    public static int[] q = new int[N], d = new int[N];

    public static void main(String[] args) {
        //n是点的数量，m是操作次数
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); m = in.nextInt();
        Arrays.fill(h, -1);

        //在节点和节点之间建立有向边，并且将被指向的节点的入度值+1
        for (int i = 0; i<m; i++){
            int x = in.nextInt(), y = in.nextInt();
            insert(x, y);
            d[y] += 1;
        }

        //如果说当前图是一个无环图，那么输出拓扑序列，如果是有环图，返回-1
        if (topsort()) {
            for (int i = 0; i<n; i++) {System.out.print(q[i] + " ");}
        }
        else {System.out.println("-1");}
    }

    //拓扑排序
    public static boolean topsort() {
        //hh和tt模拟队列的头和尾，再将所有入度为0的节点插入到队列中
        int hh = 0, tt = -1;
        for (int i = 1; i<=n; i++){
            if (d[i]==0) {q[++tt] = i;}
        }

        //循环队列不为空，将队列头节点取出，拿到这个节点的所有指向下标
        while (hh<=tt) {
            int t = q[hh++];
            for (int i = h[t]; i!=-1; i = ne[i]) {
                int j = e[i];        //根据指向下标拿到节点值，将节点的入度减一，因为指向它的节点少了一个
                d[j] -= 1;
                if (d[j]==0) {       //如果说这个节点的入度为0了，那么说明这个节点符合拓扑序列的规则，将节点加入到队列中
                    q[++tt] = j;
                }
            }
        }

        //返回的话，判断一下tt也就是整个队列出现过多少个节点，如果节点数==n的话，说明这是无环图，反之就是有环图
        //注意一下，这里n-1是因为我们的tt初始是-1
        return tt == n-1;
    }
    
    //模拟再单链表头插入
    public static void insert(int x, int y) {
        e[index] = y; ne[index] = h[x]; h[x] = index++;
    }
}
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

图例：
出度：指的是从这个点出发的边的数量
入度：指的是这个点被几条边指向
拓扑序列：
如果一个有向无环图可以排列成所有箭头指向一个方向，没有反方向箭头的话，就是拓扑序列
有环图的话，至少会有一个箭头是反方向的，所以有环图不符合拓扑序列

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流