首页 > 代码库 > 有向拓扑排序的应用
有向拓扑排序的应用
有向拓扑排序的应用
首先输入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<Integer>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]+" "); }}
有向拓扑排序的应用
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。