def. Directed Acyclical Graph (DAG). No shit.
- Directed Trees are (obviously) DAGs.
- It also has a topological ordering
Algorithm Problem Tips. Detecting if a Directed Graph is Acyclic.
- Idea: DFS with tree. If there is no back edge, it is a DAG.
alg. Topological Sort (DFS). DFS with preand post-times. Order by decreasing post-time.
- See Also course
- Topological Sort may not be unique
alg. Shortest Path for DAG. Idea: Topological sort of DAG. Then, linearly calculate minimum distance to that. slides