Properties of DFS

Dependencies:

1. Graph
2. Transpose of a graph
3. Forest
4. Rooted tree

$$ $$ $$ $$ Depth-first search (DFS) is an algorithm which systematically explores a graph $G=(V,E)$.

It returns a DFS forest of $G$ and discovery-start-time and discovery-finish-time for each vertex.

The algorithm

DFS maintains 5 attributes for every vertex:

• Start time: $s:V\mapsto \mathbb{N}$
• Finish time: $f:V\mapsto \mathbb{N}$
• $\pi :V\mapsto V\cup \{\text{null}\}$
• $\mathrm{color}:V\mapsto \{\text{black},\text{gray},\text{white}\}$
• $\mathrm{depth}:V\mapsto \mathbb{N}$

Initially, for every vertex $v$, $s(v)=f(v)=0$, $\pi (v)=\text{null}$, $\mathrm{color}(v)=\text{white}$, and $\mathrm{depth}(v)=0$.

Let $\mathrm{adj}(u)=\{v\in V:(u,v)\in E\}$.

DFS algorithm on $G$:

for u in G.V:
    color[u] = white
    π[u] = null
time = 0

def visit(u, d):
    assert(color[u] == white)
    depth[u] = d
    color[u] = gray
    time += 1
    s[u] = time
    for v in adj[u]:
        if color[v] == white:
            π[v] = u
            visit(v, d+1)
    color[u] = black
    time += 1
    f[u] = time

for u in G.V:
    if color[u] == white:
        visit(u, 0)

As visit(u) iterates over adj[u], we say that the edge $(u,v)$ is explored for $v\in \mathrm{adj}(u)$.

Vertices with depth 0 are called root vertices. When DFS terminates, root vertices are the only vertices to have $\pi (u)=\text{null}$, since $\pi (v)$ is set to a vertex before all non-root visit(v) calls.

When DFS terminates, $\pi$ can be interpreted as a graph $G_{\pi }=(V,E_{\pi })$ where $(u,v)\in E_{\pi }⟺\pi (v)=u\ne \text{null}$. Since $\pi (v)$ is set to $u$ only for $v\in \mathrm{adj}(u)$, $G_{\pi }\subseteq G$. Therefore, $G_{\pi }$ is called the predecessor subgraph of $G$.

Properties of DFS

• visit is called on each vertex exactly once, because visit is only called on white vertices and visit(u) makes $u$ gray before any recursive calls.

• During the execution of DFS, whenever time is set, the following invariant holds on $\mathrm{color}(u)$:

  • If visit(u) hasn't yet been called, $u$ is white.
  • If visit(u) was called but visit(u) hasn't ended, $u$ is gray.
  • If visit(u) has ended, $u$ is black.

• $G_{\pi }$ is acyclic because for every edge $(v,u)$ in $G_{\pi }$, $\mathrm{depth}(v)=\mathrm{depth}(u)+1$. Since $G_{\pi }$ is an acyclic predecessor graph, it is a union of rooted trees. Therefore, $G_{\pi }$ is also called the DFS forest of $G$.

• visit(v) was called during visit(u) iff $v$ is a descendant of $u$ in $G_{\pi }$. Proof: $$\begin{array}{rl}& \mathrm{visit}(v)\text{ was called during }\mathrm{visit}(u)\\ & ⟺\mathrm{\exists }{w}_0,w_1,\dots ,w_k,\text{ such that }(w_0=u\wedge w_k=v\wedge (\mathrm{\forall }1\le i<k,\mathrm{visit}(w_i)\text{ made a direct call to }\mathrm{visit}(w_{i+1})))\\ & ⟺\mathrm{\exists }{w}_0,w_1,\dots ,w_k,\text{ such that }(w_0=u\wedge w_k=v\wedge (\mathrm{\forall }1\le i<k,\pi (w_{i+1})=w_i))\\ & ⟺\text{ there is a path in }{G}_{\pi }\text{ from }u\text{ to }v\end{array}$$

• DFS takes $\mathrm{\Theta }(|V|+|E|)$ time to run, because it visits each vertex exactly once and reads its adjacency list during the visit.

• During DFS, the function call stack can have at most $|V|$ visit calls. DFS also stores attributes for each vertex. Therefore, its auxiliary memory requirement is $O(|V|)$.

Dependency for:

1. DFS: Parenthesis theorem
2. DFS: Edge classification
3. DFS: White-path theorem
4. DFS: low

Info:

• Depth: 3
• Number of transitive dependencies: 8

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Transpose of a graph
6. Path in Graph
7. Rooted tree
8. Forest