# Depth-First Search - Defined as starting from multiple sources, until all vertices are traversed. - _Predecessor subgraph_: $G_\pi = (V, E_\pi)$, where $E_\pi = \{(v_\pi, v) : v \in V, v.\pi \ne \text{NIL}\}$, a _depth-first forest_ consists of multiple _depth-first [[tree|trees]]_. - Two _timestamps_: _discover time_ $u.d$ and _finish time_ $u.f$. i.e. $u$ is white before $u.d$, gray between $u.d$ and $u.f$, and black after $u.f$. - $\Theta(V + E)$ - Parenthesis structure - Four types of edges in $G$ - Tree edges, edges in $G_\pi$ - Back edges, proper descendants to predecessors - Forward edges, predecessors to proper descendants - Cross edges - DFS trees of unweighted graph contain only tree edges and back edges. - A directed graph is acyclic iff $G$ yields no back edges. - Very hard to [[parallelism|parallelize]]!