挑战程序设计竞赛（算法和数据结构）——15.2拓扑排序（dfs，bfs）的JAVA实现

题目&＃xff1a;

代码&＃xff1a;

import java.util.*;public class TopologicalSort {public static void main(String[] args) {Scanner cin &＃61; new Scanner(System.in);int N &＃61; cin.nextInt();boolean V[] &＃61; new boolean[N];for (int i&＃61;0;i<N;i&＃43;&＃43;){V[i] &＃61; false;}int indegree[] &＃61; new int[N];ArrayList<Integer> A[] &＃61; new ArrayList[N];for (int i&＃61;0;i<N;i&＃43;&＃43;){A[i] &＃61; new ArrayList<>();}int M &＃61; cin.nextInt();for (int i&＃61;0;i<M;i&＃43;&＃43;){int s &＃61; cin.nextInt();int t &＃61; cin.nextInt();indegree[t]&＃43;&＃43;;A[s].add(t);}LinkedList<Integer> out &＃61; myTopologicalSort(V, indegree, N, A);for (int element : out){System.out.println(element);}}public static LinkedList<Integer> myTopologicalSort(boolean[] V, int[] indegree, int n, ArrayList<Integer> A[]){LinkedList<Integer> out &＃61; new LinkedList<>();String mode &＃61; "dfs";if(mode.equals("bfs")){for (int u&＃61;0;u<n;u&＃43;&＃43;){if(indegree[u]&＃61;&＃61;0 && !V[u]){out &＃61; bfs(u, V, indegree, out, A);//对于所有节点中的每一个节点运用bfs算法}}}else if(mode.equals("dfs")){for (int s &＃61; 0; s <n; s&＃43;&＃43;){if(!V[s]){out &＃61; dfs(s, V, out, A);}}Collections.reverse(out);}return out;}public static LinkedList<Integer> dfs(int u, boolean[] V, LinkedList<Integer> out, ArrayList<Integer> A[]){V[u] &＃61; true;for (int i &＃61; 0; i<A[u].size(); i&＃43;&＃43;){int v &＃61; A[u].get(i);//u的邻接点if(!V[v]){dfs(v, V, out, A);}}out.add(u);return out;}public static LinkedList<Integer> bfs(int s, boolean[] V, int[] indegree, LinkedList<Integer> out, ArrayList<Integer> A[]){Queue<Integer> Q;Q &＃61; new ArrayDeque();//将当前节点设为处理中状态Q.add(s);V[s] &＃61; true;//只要Q队列不为空就执行循环操作&＃xff0c;广度搜索while(Q.size()!&＃61;0){int u;//只有队头元素的入度为0时&＃xff0c;才可以将其添加至outu &＃61; Q.remove();V[u] &＃61; true;//删除Q的队头元素&＃xff0c;并将队头元素赋给outout.add(u);//对于第u个节点的所有出度for (int i&＃61;0;i<A[u].size();i&＃43;&＃43;){int v &＃61; A[u].get(i);//u的邻接点indegree[v]--;//如果v的入度为0且还没有被处理过if(indegree[v]&＃61;&＃61;0 && !V[v]){V[v] &＃61; true;Q.add(v);}}}return out;}
}


输入&＃xff1a;

6 6
0 1
1 2
3 1
3 4
4 5
5 2


bfs输出&＃xff1a;

0
3
1
4
5
2


dfs输出&＃xff1a;

3
4
5
0
1
2