Skip to content

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_\pi = (V, E_\pi)\)
  • 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

img

Complexity

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

Properties of DFS

  • 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\)

Classification of edges

4 types of edges:

  • tree edges are edges in depth-first forest \(G_\pi\) 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