Review: Topological Sort Problems Posted on August 5, 2019July 26, 2020 by braindenny Topological Sort Problems CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Basic Abstractions Name Summary Wikipedia: Topological sorting Kahn’s algorithm, DFS algorithm unexamined nodes with no incoming edges Unused edge Top Questions Name Example Time complexity should be O(n+e) O(n2) would work, but not optimal Indegrees as a list of 0s might troublesome Use hashmap instead LeetCode: Sequence Reconstruction What if duplicate edges would be given For edges datastructure, use hashmap instead of list Common Mistake: Missing characters without incoming edges LeetCode: Alien Dictionary Common Mistake: Avoid updating indegrees repetitively for duplicate edges LeetCode: Alien Dictionary Common Mistake: in dfs implementation, process 0-degree nodes multiple times LeetCode: Alien Dictionary Longest path in a DAG without circle LeetCode: Longest Increasing Path in a Matrix Topoloical sort: How to return all possible orders, instead of any one? For nodes in connections, in the form of intergers or strings? Topoloical sort(BFS): doesn’t need a visited hashmap LeetCode: Course Schedule II Code Skeleton Solution: Kahn’s algorithm (BFS) without deleting edges // https://code.dennyzhang.com/course-schedule // Basic Ideas: topological sort + Kahn's algorithm // // BFS // queue: unexamined nodes with no incoming edges // Decrease count of incoming edges for the target nodes // Get the next nodes to be examined // // When to stop? // When BFS stops, there should be no unexamined edges // Or all nodes get examined // // Follow-up: what if there are duplicate edges? // // Complexity: Time O(n+e), Space O(n+e) func canFinish(numCourses int, prerequisites [][]int) bool { indegrees := make([]int, numCourses) edges := map[int]map[int]bool{} for _, p := range prerequisites { n1, n2 := p[0], p[1] if _, ok := edges[n1]; !ok { edges[n1] = map[int]bool{} } edges[n1][n2] = true indegrees[n2]++ } count := 0 queue := []int{} for i, v := range indegrees { if v == 0 { queue = append(queue, i) count++ } } for len(queue) > 0 { l := []int{} for _, n1 := range queue { for n2, _ := range edges[n1] { indegrees[n2]-- if indegrees[n2] == 0 { l = append(l, n2) count++ } } } queue = l } return count == numCourses } Topological sorting forms the basis of linear-time algorithms for finding the critical path of the project, a sequence of milestones and tasks that controls the length of the overall project schedule. See all topologicalsort problems: #topologicalsort Review: Topological Sort ProblemsLeetCode: Sort Items by Groups Respecting DependenciesLeetCode: Sequence ReconstructionLeetCode: Redundant Connection IILeetCode: Parallel CoursesLeetCode: Loud and RichLeetCode: Longest Increasing Path in a MatrixLeetCode: Find Eventual Safe StatesLeetCode: Course Schedule IILeetCode: Course ScheduleLeetCode: Alien Dictionary See more blog posts. Post Views: 0