一、什么是拓扑排序
在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
每个顶点出现且只出现一次。 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。
例如，下面这个图：
它是一个 DAG 图，那么如何写出它的拓扑排序呢？这里说一种比较常用的方法：
从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。 从图中删除该顶点和所有以它为起点的有向边。 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
于是，得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。
通常，一个有向无环图可以有一个或多个拓扑排序序列。
二、拓扑排序的应用
拓扑排序通常用来“排序”具有依赖关系的任务。
比如，如果用一个DAG图来表示一个工程，其中每个顶点表示工程中的一个任务，用有向边
import java.util.Scanner; public class 拓扑排序 { /** * @param args */ private static int dege[][]=null; private static int cnt[]=null; public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scanner(System.in); int n,m; n=scan.nextInt(); m=scan.nextInt(); dege=new int[n][n]; cnt=new int[n]; for(int i=0;i<n;i++){ int a=scan.nextInt(); int b=scan.nextInt(); dege[a-1][b-1]=1; cnt[b-1]++; } TopoOrder(n); } private static void TopoOrder(int n) { // TODO Auto-generated method stub int top=-1; for(int i=0;i<n;i++){ if(cnt[i]==0){ cnt[i]=top; top=i; } } for(int i=0;i<n;i++){ if(top==-1){ System.out.println("回路"); return ; } else{ int j=top; top=cnt[top]; System.out.print(j+" "); for(int k=0;k<n;k++){ if(dege[j][k]==1&&(--cnt[k])==0){ cnt[k]=top; top=k; } } } } } }