拓扑图算法题-Acwing848. 有向图的拓扑序列

本文主要是介绍拓扑图算法题-Acwing848. 有向图的拓扑序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前置知识

在图论中，拓扑排序是对有向无环图（DAG，Directed Acyclic Graph）进行的一种排序。在拓扑排序中，有两个重要的概念，即“入度”和“出度”。

入度（In-Degree）：
- 对于有向图中的每个顶点，入度表示指向该顶点的边的数量。
- 具体说，如果存在一条边从顶点 A 指向顶点 B，那么顶点 B 的入度就加 1。
- 入度反映了图中某个节点作为终点的频率，即有多少条边指向该节点。
出度（Out-Degree）：
- 对于有向图中的每个顶点，出度表示从该顶点出发的边的数量。
- 具体说，如果存在一条边从顶点 A 出发指向顶点 B，那么顶点 A 的出度就加 1。
- 出度反映了图中某个节点作为起点的频率，即有多少条边从该节点出发。

在拓扑排序中，一般首先选取入度为 0 的节点作为起始节点，然后不断删除起始节点并更新其相邻节点的入度，直至所有节点被遍历。这样得到的顺序即为拓扑排序。

关于拓扑排序的算法步骤：

统计每个节点的入度。
将入度为 0 的节点加入队列。
遍历队列，每次取出一个节点，更新其相邻节点的入度。
将入度为 0 的相邻节点加入队列。
重复步骤 3-4，直到队列为空。

拓扑排序常用于表示任务的依赖关系，例如工程项目的任务安排，编译过程中源文件的编译顺序等。

题目

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

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

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

输入格式

第一行包含两个整数 n和 m。

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

输出格式

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

否则输出 −1。

数据范围

1≤n,m≤105

输入样例：

输出样例：

1 2 3

代码与解析

构建有向图：通过输入的边信息构建有向图，同时统计每个节点的入度。
拓扑排序：将所有入度为 0 的节点加入队列，然后依次取出队列中的节点，更新其邻接节点的入度，并将新的入度为 0 的节点加入队列。循环直到队列为空。
判断是否有环：如果拓扑排序得到的节点数等于总节点数，说明图中无环，可以进行拓扑排序；否则，说明图中存在环，无法进行拓扑排序。

import java.util.*;public class TopologicalSort {static int n, m, idx, N = 100010, record;static int[] e = new int[N], ne = new int[N], h = new int[N], dis = new int[N];static Queue<Integer> q = new LinkedList<>();static List<Integer> list = new ArrayList<>();// 添加有向边public static void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;}public static void main(String[] args) {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 a = in.nextInt();int b = in.nextInt();add(a, b);dis[b]++;}if (topSort()) {// 输出拓扑排序结果for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}} else {// 说明图中存在环，无法进行拓扑排序System.out.println(-1);}}// 拓扑排序private static boolean topSort() {for (int i = 1; i <= n; i++) {// 将入度为 0 的节点加入队列if (dis[i] == 0) {q.offer(i);}}while (!q.isEmpty()) {record++;int t = q.poll();list.add(t);// 遍历以 t 为起点的所有边for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];dis[j]--;// 如果节点 j 的入度为 0，则加入队列if (dis[j] == 0) {q.offer(j);}}}// 如果拓扑排序得到的节点数等于总节点数，说明无环，返回 truereturn record == n;}
}