拓扑序列（拓扑排序）

大家好，欢迎来到IT知识分享网。

摘要

本文主要介绍拓扑序列，和求解拓扑序列的方法。

什么是拓扑序列

拓扑序列是对于有向图而言的，有向图的拓扑序是其顶点的线性排序，使得对于从顶点$u$ 到顶点$v$的每个有向边$uv$， $u$ 在序列中都在$v$之前。

1. 每个顶点只出现一次。
2. 对于图中的任何一条边，起点必须在终点之前。

拓扑序的求法

首先，不是所有的有向图都是有拓扑序的，只有有向无环图才有拓扑序，所以有向无环图又被称为拓扑图。

拓扑序是按照点的先后顺序排列的，也就是说入度为0的点一定是排在前面的，我们直接对一个图BFS一遍，BFS过程中更新每个点的入度，如果一个点的入度为0，那么就将其加入拓扑序，并且删除其与后继结点的所有边。

在读入边的时候，直接计算点的入度。

代码：

import java.io.*; import java.util.*; public class Main{ 
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); static final int N = ; static int n, m, idx = 1; static int e[] = new int[N]; static int ne[] = new int[N]; static int h[] = new int[N]; static int d[] = new int[N]; static Queue<Integer> q = new LinkedList<>(); static Queue<Integer> ans = new LinkedList<>(); public static int Int(String s){ 
   return Integer.parseInt(s);} public static void add(int a, int b){ 
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } public static Boolean bfs(){ 
    while(!q.isEmpty()){ 
    int x = q.peek(); q.poll(); for(int i = h[x]; i != 0; i = ne[i]){ 
    // 遍历所有后继结点 if(--d[e[i]] == 0){ 
   // 删除当前点与后继结点的边，如果删除后 //其后继结点的入度变为0，就入队 q.add(e[i]); ans.add(e[i]); } } } if(ans.size() == n) return true; else return false; } public static void main(String[] args) throws IOException{ 
    String[] s = in.readLine().split(" "); n = Int(s[0]); m = Int(s[1]); for(int i = 0; i < m; i++){ 
    String s1[] = in.readLine().split(" "); add(Int(s1[0]), Int(s1[1])); d[Int(s1[1])] ++; // 入度加一  } int flag = 0; for(int i = 1; i <= n; i++){ 
    if(d[i] == 0){ 
    // 找到入度为0的点 q.add(i); ans.add(i); flag = 1; } } if(flag == 0) out.write("-1\n"); else { 
    if(bfs()){ 
    // 输出拓扑序 while(!ans.isEmpty()){ 
    out.write(ans.poll()+" "); } } else{ 
    // 不存在拓扑序 out.write("-1\n"); } } out.flush(); } }