【算法】有向图的拓扑排序

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

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

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围
1≤n,m≤105
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3

原题链接

涉及的点

• 只有有向图才有拓扑排序
• 有向无环图中一定存在一个入度为0的点
• 一个图只要有环，就一定没有拓扑排序，无环一定有拓扑排序
• java建立邻接表方式之一
  • 用一个 List<List> g, 建立 a指向 b的点就是 g.get(a).add(b),g.get(a)能获取所有以a为起点的集合

思路

1. 将入度为0的点加入到队列中

2. 再删去该点，删去的代价就是该点所指向的点入度 -1

3. 再将已经是入度为0的点加入，逐个击破

4. 若输出的顶点数小于图中的顶点数，则表示该图存在回路，即无法拓扑排序，

   否则，输出的就是拓扑序列 （不唯一）

code

import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] d = new int[n + 1];
        List<List<Integer>> g = new ArrayList<>();
        
        //构建邻接表
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        while(m -- > 0){
            int a = sc.nextInt(),b = sc.nextInt();
            g.get(a).add(b);
            d[b] ++;
        }
        
        Queue<Integer> q = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        
        for(int i = 1; i <= n; i ++){
            if(d[i] == 0){
                q.add(i);
            }
        }
        
        while(q.size() > 0){
            int t = q.poll();
            res.add(t);
            for(int i : g.get(t)){
                if(-- d[i] == 0){
                    q.add(i);
                }
            }
        }
        if(res.size() == n){
            for(int x : res){
                System.out.print(x + " ");
            }
        }else{
            System.out.println(-1);
        }
    }
}