Depth-First Search

Summarized notes on Introduction to Algorithms, Chapter 22

works on both directed and undirected graphs
explores edges out of the most recently discovered vertex $v$ that still has unexplored edges leaving it
after $v$ is fully search, backtracks to explore vertex from which $v$ was discovered
if any undiscovered vertices remain, DFS selects one as a new source and repeats the search
search continues until every vertex has been discovered
predecessor subgraph of DFS forms a depth-first forest and may consists of many trees → defined as $G_{π} = (V, E_{π})$
Edge coloring in DFS
- all vertices start out as white
- vertex is greyed when it is discovered
- vertex becomes black when it is finished
- this strategy guarantees vertex can be in exactly one depth-first tree
DFS also uses timestamps
- $v . d$ - discovery time - when vertex becomes grey
- $v . f$ - finish time - when vertex becomes black
- integers in range 1 - 2 $| V |$ and $v . d < v . f$ , always
- these timestamps help with analysis later
the result of DFS may vary depending on the order in which neighboring vertices are visited → in practice this is not an issue

Complexity

Running Time
$O (V + E)$	DFS is linear time

result is a forest of trees
vertex $v$ is decedent of $u$ if and only if $v$ discovered during the time $u$ is grey
vertex $v$ is a descendant of $u$ if and only if at the time $u . d$ there is a path from $u$ to $v$ consisting entirely of white vertices
discovery and finishing times have parentheses structure, i.e. open before close
parentheses theorem: for any two vertices $v$ and $u$ 1 of 3 is true:
1. intervals $[u . d, u . f]$ and $[v . d, v . f]$ are entirely disjoint and neither is decedent of the other
2. interval $[u . d, u . f]$ is contained entirely within $[v . d, v . f]$ → $u$ is decedent of $v$
3. interval $[v . d, v . f]$ is contained entirely within $[u . d, u . f]$ → $v$ is decedent of $u$
vertex $v$ is a proper descendant of $u$ if and only if $u . d < v . d < v . f < u . f$

4 types of edges:

tree edges are edges in depth-first forest $G_{π}$ discovered by exploring
back edges connect vertex to its ancestor in depth-first tree
forward edges nontree edges, connect vertex to a descendant
cross edges all other edges; can connect different trees or connect vertices where one is not ancestor of the other
During exploration vertex color indicates the type of edge (see picture above):
1. white vertex means edge is a tree edge
2. gray means a back edge
3. black is forward or cross edge
For undirected graph it maybe difficult to classify edges
- use first type that applies
- all edges are either tree or back edges