Topological Sort Problems

**Basic Abstractions**

Name | Summary |
---|---|

unexamined nodes with no incoming edges | |

Unused edge | |

Wikipedia: Topological sorting | Kahn’s algorithm, DFS algorithm |

**Questions**

Name | Example |
---|---|

Time complexity should be O(n+e) | O(n^2) would work, but not optimal |

Indegrees as a list of 0s might troublesome | Use hashmap instead Leetcode: Sequence Reconstruction |

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 |

Topoloical sort: How to return all possible orders, instead of any one? | |

Longest path in a DAG without circle | Leetcode: Longest Increasing Path in a Matrix |

For nodes in connections, in the form of intergers or strings? |

**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 Problems
- Leetcode: Sort Items by Groups Respecting Dependencies
- Leetcode: Sequence Reconstruction
- Leetcode: Redundant Connection II
- Leetcode: Parallel Courses
- Leetcode: Loud and Rich
- Leetcode: Longest Increasing Path in a Matrix
- Leetcode: Find Eventual Safe States
- Leetcode: Course Schedule II
- Leetcode: Course Schedule
- Leetcode: Alien Dictionary

See more blog_posts.