dfs

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 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 parallelize!