对于一个有向无环图G=(V,E)来说，拓扑排序就是G中所有结点的一种线性次序，该次序满足如下条件：其结点u在拓扑排序中处于v的前面(如果图G包含环路，则不可能排出一个线性次序)，可以将图的拓扑排序看作是将图的所有结点在一条水平线上展开，在该水平线上，所有的有向边都是从左向右。
我们构造拓扑排序主要循环一下两步：
1)选择一个入度为0的顶点并输出;
2)从网中删除此顶点以及所有出边;
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
以下图为例，来说明拓扑排序算法的执行过程
(1) 在(a)图中v0和v1的入度都为0，不妨选择v0并输出之，接着删去顶点v0及出边<0,2>，得到的结果如(b)图所示。
(2) 在(b)图中只有一个入度为0的顶点v1，输出v1，接着删去v1和它的三条出边<1,2>,<1,3>和<1,4>，得到的结果如(c)图所示。
(3) 在(c)图中v2和v4的入度都为0，不妨选择v2并输出之，接着删去v2及两条出边<2,3>和<2,5>，得到的结果如(d)图所示。
(4) 在(d)图上依次输出顶点v3,v4和v5，并在每个顶点输出后删除该顶点及出边，操作都很简单，不再赘述。
在拓扑排序算法中，需要用一个一维数组来保存各个顶点的入度值，recode[]
顶点： 0 1 2 3 4 5
入度： 0 0 2 2 1 3
看网上有各种算法，有的用栈，有的用队列，但是我自己在里面嵌套了一个循环所有结点是否访问过，如果有没访问过的,即visited[i]==0,那么继续从头开始遍历点，这样做复杂度会高一些，但是比较容易理解。
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; /* * 我们应该将焦点集中在入度上，当这个定点的所有入边对应的定点都被访问过，那么才能访问该节点 */ public class Test { static int edge,node; //边数、顶点数 static int [][]map=new int[20][20]; static int [] visited=new int [20]; static int [] recode=new int [20]; //记录入度 static int [] recode1=new int [20]; static Queue<Integer> q=new LinkedList<Integer>(); static boolean falg; static Scanner sc=new Scanner(System.in); public static void main(String[] args) { int f,t; falg=false; edge=sc.nextInt(); node=sc.nextInt(); for(int i=0;i<=node;i++) {visited[i]=0;recode[i]=0;recode1[i]=0;} for(int i=1;i<=edge;i++){ f=sc.nextInt(); t=sc.nextInt(); map[f][t]=1; //代表从f->t存在边。 recode[t]++; } while(falg!=true){ for(int i=1;i<=node;i++){ if(recode[i]==0&&visited[i]==0){ System.out.println(i); visited[i]=1; for(int j=1;j<=node;j++){ if(map[i][j]==1) {map[i][j]=0;recode[j]--;} } } int num=0; for(int j=1;j<=node;j++){ if(visited[j]==1) num++; } if(num==node) falg=true; //如果所有点都访问过，那么应该结束循环 } } } }