Depth First Search

alg. Depth First Search. DFS, but also record the preand post-times as it is convenient. From Class:

• Time Complexity: $O(V+E)$
• DFS is useful in most graph tasks except Shortest Path (that’s for BFS)

thm. Identifying DAGs. If there is no back edge, the graph is a DAG.

alg. DAG Topological Ordering. Perform DFS with postand pre-time. Check there are no back edges (i.e. no cycle)