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