Part VI · Graph Algorithms and Tree-Graph Techniques
34. Directed Acyclic Graphs and Topological Ordering
6 lessons•23 topics•Intermediate / Advanced
6 of 6 lessons published
34.014 animated
Directed graph fundamentals
- In-degree/out-degree
- Sources/sinks
- Directed cycles
- Forward and reverse edges
34.023 animated
Topological sort
- Kahn's algorithm
- DFS finish-order method
- Cycle detection via incomplete ordering
34.035 animated
Topological order applications
- Course schedule
- Build dependencies
- Task prerequisites
- Alien dictionary
- Package dependencies
34.044 animated
DAG algorithms
- Longest path in DAG
- Shortest path in DAG
- Count paths
- DP over topological order
34.054 animated
Directed reachability
- Ancestor queries
- Descendants
- Transitive closure
- Reversed DAG
34.063 animated
Strongly connected components intro
- SCC definition
- Condensation graph
- Why condensation is a DAG