2 methods for Topological Sort : BFS / DFS


  • 0
    M

    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) {
                map.get(p[1]).add(p[0]);
                ++inD[p[0]];
            }
            Queue<Integer> q = new LinkedList<>();
            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) {
                adj.get(p[1]).add(p[0]);
            }
            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;
        }
    

Log in to reply
 

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