Depth First Search

Tags: algorithm comp-sci

Is an algorithm for [see page 7, traversing] all the nodes of a graph. It works by exploring recursively down to the root of each node, before back tracking up and exploring sibling nodes.

time = 0

def dfs(g):
    global time
    time = 0
    for v in g.vertices():
	v.color = white
	v.search_parent = None
    for u in g.vertices():
	if u.color == 'white':
	    dsf_visit(g, u)

def dfs_visit(g, u):
    global time
    time += 1
    u.d = time
    u.color = 'gray'
    for v in u.edge_vertices():
	if v.color == 'white':
	    v.search_parent = u
	    dfs_visit(g, v)
    u.color = 'black'
    time = time + 1
    u.f = time

Code Snippet 1: Depth first search implementation (see see page 15, [here]). This implementation stores the time step at which we start a depth first search on a node as \( u.d \) and when we finish traversing the algorithm as \( u.f \). See it in action see page 17, [here].

Being implemented recursively means DFS implicitly uses a stack to store vertices while exploring the graph.

As for BFS, DFS defines predecessors that [see page 13, represent] several Depth First Trees each of which form a Depth First Forest.

DFS can be used to [see page 23, classify] edges and detect cycles in directed graphs.

[see page 19, Parenthesis Structure]

For any two vertices \( u \neq v \), either:

dfs_visit(v) is called during dfs_visit(u) then v is a descendent of u and dfs_visit(v) finishes earlier than u. \[ u.d < v.d < v.f < u.f \]
The same happens with the rules of \( v \) and \( u \) swapped. \[ v.d < u.d < u.f < d.f \]
The intervals \( [u.d, u.f] \) and \( [v.d, v.f] \) are entirely disjoint and neither \( u \) nor \( v \) are a descendent of each other.

[see page 20, White Path Theorem]

In a depth first forest vertex \( v \) is a descendent of a vertex \( u \) if and only if at time \( u.d \) there is a path from \( u \) to \( v \) consisting entirely of white vertices.