BFS / Topological Sort

相关文章：DFS

Difference between Topological Sort & BFS

Topological Sort 只需要保证一条路径上先出现的node一定排在后出现的node前即可，对兄弟路径的排序并无要求，BFS中兄弟路径中深度相同的node必须要排在一起，深度大的node要排在深度小的node之前。

Tree实现 BFS / Topological Sort

1. 将root推入queue
2. 弹出queue中的node，将左右子树推入

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        Queue<TreeNode> cur_level = new LinkedList<>();
        cur_level.add(root);
        while (!cur_level.isEmpty()) {
            int cur_size = cur_level.size();
            List<Integer> level_ans = new LinkedList<>();
            while (cur_size>0) {
                TreeNode cur_node = cur_level.poll();
                if (cur_node != null) {
                    level_ans.add(cur_node.val);
                    cur_level.add(cur_node.left);
                    cur_level.add(cur_node.right);
                }
                cur_size--;
            }
            if (level_ans.size() > 0) {
             ans.add(level_ans);
            }
        }
        return ans;
}

N = number of tree nodes
时间复杂度：O(N)
空间复杂度：O(N) for the queue

Graph实现 BFS / Topological Sort

入度 (indegree) ：有多少条edge指向目标节点
出度 (outdegree) ：有多少条edge从目标节点出发

1. 寻找入度为0的node，推入queue
2. 弹出queue中的node，遍历它们通往的nodes，减小入度，如果入度减小为0，推入queue
3. 重复步骤2

public boolean canFinishTopological(int numCourses, int[][] prerequisites) {
        //indegrees[i]: how many node should be visited before visit i
        int[] indegrees = new int[numCourses];
        //key: the start node   value: a list of the end node
        HashMap<Integer, ArrayList<Integer>> edges = new HashMap<>(); 
        
        //initialize indegrees and edges
        for (int[] p : prerequisites) {
            indegrees[p[0]]++;
            if (!edges.containsKey(p[1])) {
                edges.put(p[1], new ArrayList<Integer>());
            } 
            ArrayList<Integer> destList = edges.get(p[1]);
            destList.add(p[0]);
        }
        
        //push nodes with not income to queue for poping them first
        Queue<Integer> queue = new LinkedList<>();
        for (int i=0; i<indegrees.length; i++) {
            if (indegrees[i] == 0) {
                queue.add(i);
            }
        }
        
        //topological sort
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            numCourses--;
            if (edges.containsKey(curr)) {
                for (int next : edges.get(curr)) {
                    indegrees[next]--;
                    if (indegrees[next] == 0) {
                        queue.add(next);
                    }
                }
            }
        }
        return numCourses == 0;
}

N = number of graph nodes, M = number of edges
时间复杂度：O(N+M)
空间复杂度：O(N) for the indegree array, O(M) for the edges HashMap, so O(N+M) in total

相关练习

Tree

Leetcode CN 102 - 二叉树的层序遍历
Leetcode CN 107 - 二叉树的层序遍历II

Matrix

Leetcode CN 547 - 朋友圈
Leetcode CN 417 - 太平洋大西洋水流问题

Graph

Leetcode CN 207 - 课程表

参考文献