Topological Sort Problems

**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(n^{2}) 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 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.