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