本文共 1486 字,大约阅读时间需要 4 分钟。
package Graph;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class TopSortInQueue { LinkedList[]adj; boolean []book;//标记是否是顶点 (可以处理顶点不连续的情况) final int MAX = 100;//预设的最大顶点的序号(并非顶点数目) int v, e; public static void main(String[] args) { new TopSortInQueue().run(); } public void run() { Scanner in = new Scanner(System.in); v = in.nextInt(); e = in.nextInt(); book = new boolean[MAX]; adj = new LinkedList[MAX];//这里不能是顶点个数大小因为顶点可能不连续 for(int i = 0; i < adj.length; i++ ) {//这里需要时adj.length因为 顶点 可能不连续 adj[i] = new LinkedList<>(); } for(int i = 0; i < e; i++ ) { int a = in.nextInt(); int b = in.nextInt(); adj[a].offer(b); book[a] = true; book[b] = true; }// for(int i = 0; i < adj.length; i++ ) {// System.out.println(adj[i]);// } topSort(); } public void topSort() { int []ins = new int[MAX];//记录各节点入度 int []rel = new int[v];//记录排序结果 Queue que = new LinkedList<>(); for(int i = 0; i < adj.length; i++ ) { for(int w:adj[i]) { ins[w]++; } } for(int i = 0; i < v; i++ ) { if(ins[i] == 0 && book[i]) {//是顶点 并且 入度为 0 入队 que.offer(i); } } int cnt = 0; while(!que.isEmpty()) { int v = que.poll(); rel[cnt++] = v; for(int w:adj[v]) { ins[w]--; if(ins[w] == 0 && book[w]) {//是顶点 并且 入度为 0 入队 que.offer(w); } } } if(cnt != v) { System.out.print("hasCycle"); return; } else { for(int i = 0; i < cnt; i++ ) { System.out.print(rel[i]+" "); } } } }
转载地址:http://jlimi.baihongyu.com/