# 2 methods for Topological Sort : BFS / DFS

• BFS:

``````    public int[] findOrder(int numCourses, int[][] prerequisites) {
int n = numCourses;
int[] order = new int[n];
int ind = 0;
int[] inD = new int[n];
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < n; ++i) map.put(i, new ArrayList<Integer>());
for (int[] p : prerequisites) {
++inD[p[0]];
}
for (int i = 0; i < n; ++i) {
if (inD[i] == 0) {
q.offer(i);
}
}
while (!q.isEmpty()) {
int i = q.poll();
order[ind++] = i;
for (int next : map.get(i)) {
if (--inD[next] == 0) q.offer(next);
}
}
if (ind < n) return new int[0];
return order;
}
``````

DFS:

``````    public int[] findOrder(int numCourses, int[][] prerequisites) {
int n = numCourses;
Map<Integer, List<Integer>> adj = new HashMap<>();
for (int i = 0; i < n; ++i) adj.put(i, new ArrayList<Integer>());
for (int[] p : prerequisites) {
}
int[] vis = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; ++i) {
if (!dfs(i, stack, vis, adj)) return new int[0];
}
int[] ord = new int[n];
int i = 0;
while (!stack.isEmpty()) {
ord[i++] = stack.pop();
}
return ord;
}

private boolean dfs(int i, Stack<Integer> stack, int[] vis, Map<Integer, List<Integer>> adj) {
if (vis[i] == 1) return false;
if (vis[i] == 2) return true;
vis[i] = 1;
for (int next : adj.get(i)) {
if (!dfs(next, stack, vis, adj)) return false;
}
vis[i] = 2;
stack.push(i);
return true;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.