# Recursive Depth First Search (122A)

# Vertex Status

Similar to whatever first search, we assign each vertex a STATUS.

NEW: literally never seen before, all vertices start with this status
ACTIVE: seen before, but the adjacent vertices are not done processing yet
FINISHED: the vertex is seen and all its children are done processing

# Pseudocode

// main routine
function DfsSearch(G):
	for each vertex v in G:
		mark v as NEW
	for each vertex v in G:
		if v is NEW:
			DfsVisit(v)

function DfsVisit(u):
	mark u as ACTIVE
	// process when u is ACTIVE
	Preprocess(u) 
	
	for each adjacent vertex v:
		if v is NEW: 
			DfsVisit(v) 

	mark u as FINISHED
	// process when u is FINISHED
	Postprocess(u)

// globals
time = 0 
DISCOVER_TIME = {}
FINISH_TIME = {}

// main routine
function DfsSearch(G):
	for each vertex v in G:
		mark v as NEW
	for each vertex v in G:
		if v is NEW:
			DfsVisit(v)

function DfsVisit(u):
	mark u as ACTIVE
	time++
	DISCOVER_TIME[u] = time
	Preprocess(u)
	
	for each adjacent vertex v:
		if v is NEW: 
			DfsVisit(v) 

	mark u as FINISHED
	time++
	FINISH_TIME[u] = time
	Postprocess(u)

# Python: Basic DFS

Github

# Comparison with stack based Whatever First Search

WFS with Stack

Recursive

function WfsDepth(G: Graph):
	for each vertex v in G:
		mark v as NEW
	for each vertex v in G:
		if v is NEW:
			WfsVisit(G, v)
			
function WfsVisit(G: Graph, start: Vertex):
	stack = Stack()
	stack.put(start)

	while stack is not empty:
		u = stack.popFirst()
		if u is not VISITED:
			process u
			mark u as VISITED
			for each adjacent vertex v:
				stack.put(v)

function DfsSearch(G: Graph):
	for each vertex v in G:
		mark v as NEW
	for each vertex v in G:
		if v is NEW:
			DfsVisit(v)

function DfsVisit(u: Vertex):
	mark u as ACTIVE
	Preprocess(u)
	
	for each adjacent vertex v:
		if v is NEW: 
			DfsVisit(v) 

	mark u as FINISHED
	Postprocess(u)

The recursive version replaces stack.put(v) with the recursive call DfsVisit(v).

while stack is not empty is the same as coming back to the initial call (empty call stack).

Every time DfsVisit(v) is called in the main routine, a new call stack is initialized. WFS does this by calling the stack constructor.

# Runtime Analysis

For a graph with V vertices and E edges, we call the DfsVisit(v) function V times in the main routine. The total number of recursive calls inside DfsVisit(v) is E times because we will traverse each edge exactly once, so E times for the entire graph.

Therefore the total runtime is O(V+E).

# Classifying Edges and Cycle Detection

There are 4 possible types of edges:

\begin{array}{||c:cccc||}
\hline\\
\text{Tree} & &\texttt{ACTIVE}&\longrightarrow& \texttt{NEW}\\\\
\text{Back}&& \texttt{ACTIVE}&\longrightarrow& \texttt{ACTIVE}\\\\
\text{Forward}&&\texttt{ACTIVE}&\longrightarrow& \texttt{FINISHED}\\\\
\text{Cross} &&& \text{Everything else}\\\\
\hline

\end{array}

More specifically:

Source: Prof Bai’s 122A slides. Gray = Active, White = New, Black = Finished

# Edge Interpretations

At least one back edge is found \iff the graph has a cycle. So Directed Acyclic Graphs (Like a DP dependency graph) cannot have a back edge.
Found at least 1 cross or forward edge \implies the graph is directed
Read more here

# Python: DFS with edge classification

Github

Right now it only finds back and tree edges correctly, still figuring out how to find forward and cross edges