有向拓扑排序的应用

  首先输入n个点，表示有向图中有n个顶点，接下来n行， 每行输入几个数字，第i行的数字表示它们是顶点i的后继节点，输出要求保证该行的编号要在这几个数前面,当数字为0时，表示i点没有后继节点了。 就是要求输出这个有向图的拓扑序列。

[输入输出]: [样例]:

Sample Input

5

0

4 5 1 0

1 0

5 3 0

3 0

Sample Output

2 4 5 3 1

package Main;import java.util.PriorityQueue;import java.util.Queue;import java.util.Scanner;public class Main {    private int n;    private int [][]G;//邻接矩阵    private int [] indegree;//顶点的入度    private Queue
     
      que;    private int [] result;//保存结果        public Main(int n,int [] indegree,int [][]G)    {        this.n=n;        this.indegree = indegree;        this.G = G;    }                        public static void main(String[] args) {        //输出无前驱的定点优先的拓扑排序，该方法的每一步总是输出当前无前驱的顶点        Scanner input = new Scanner(System.in);        int n,x;        int[][]G;        int [] indegree;        while(input.hasNext())        {            n = input.nextInt();            indegree = new int[n+1];            G = new int[n+1][n+1];            for(int i=1;i<=n;i++)            {                for(int j=1;j<=n;j++)                {                    x = input.nextInt();                    if(x == 0)                    {                        break;                    }                    G[i][x] = 1;                    indegree[x]++;                }            }            Main ma = new Main(n,indegree,G);            ma.topoSort();        }    }    private void topoSort() {        int r=1;          que = new PriorityQueue< Integer>();          result=new int[n+1];          for (int i = 1; i <=n; i++) {            if (indegree[i] == 0)//入度为0的顶点入队                que.add(i);           }         // for(int i=1;i<=n;i++)         //   System.out.print(indegree[i]);          while (!que.isEmpty()) {             int v = que.poll();//出队             result[r++]=v;//将v保存到结果集中             for (int i = 1; i <=n; i++) {
   //删除顶点v及以v为尾的弧。                 if (G[v][i] == 1) {                   indegree[i]--;//模拟删除边                   if (indegree[i] == 0)                     que.add(i);                  }               }           }          for(int i=1;i<=n;i++)             System.out.print(result[i]+" ");            }}