1. 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

2. Pseudocode

Barebones Version

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

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

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

With Clock (122A)

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

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

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

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

• Long Version

Comparison with stack based Whatever First Search

function WFS_Depth(G):
	for each vertex v in G:
		mark v as NEW
	for each vertex v in G:
		if v is NEW:
			WFS_Visit(G, v)
			
function WFS_Visit(G, start):
	stack = Stack()
	stack.put(start)

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

function DFS_Search(G):
	for each vertex v in G:
		mark v as NEW
	for each vertex v in G:
		if v is NEW:
			DFS_Visit(v)

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

	mark u as FINISHED
	Postprocess(u)

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

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

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

3. Runtime Analysis

We call the DFS_Visit(v) function $V$ times in the main routine

The total number of recursive calls inside DFS_Visit(v) is $E$ times because we will traverse each edge exactly once. So $E$ times for the entire graph.

The total runtime is $O(V+E)$

4. Python: Basic DFS

example_unweighted_graphs.py DIRECTED_1

ECS122A-Algorithms-python-implementation/basic-DFS.py at main · tomli380576/ECS122A-Algorithms-python-implementation