文章目录
摘要什么是拓扑序列拓扑序的求法
摘要
本文主要介绍拓扑序列，和求解拓扑序列的方法。
什么是拓扑序列
拓扑序列是对于有向图而言的，有向图的拓扑序是其顶点的线性排序，使得对于从顶点
u
u
u 到顶点
v
v
v的每个有向边
u
v
uv
uv，
u
u
u 在序列中都在
v
v
v之前。
例如对于下图： 对于上图， 存在4条边：（1,3）（1,2）（2,4）（2,3） 该图的拓扑序必须要满足以下两点：
每个顶点只出现一次。对于图中的任何一条边，起点必须在终点之前。
拓扑序的求法
首先，不是所有的有向图都是有拓扑序的，只有有向无环图才有拓扑序，所以有向无环图又被称为拓扑图。
拓扑序是按照点的先后顺序排列的，也就是说入度为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 = 100010;
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
static Queue
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();
}
}