Depth-First Search

AlgorithmsCodingDataStructuresGraphTheory A depth-first search is an algorithm to iterate through a graph such that one starts at a root (possibly arbitrary) and explores a branch completely before trying another branch.

Depth first search is useful when

• We want to visit every node in
• We want to perform a tree traversal

Complexity:

Time: O(|V| + |E|)
Space: O(|V|)

Recursive

visited = {}
def dfs(root):
	if root != None:
		f(root)
		visited[root] = True
		
		for n in root.adjacent:
			if not visited[n]:
				dfs(n) 

Iterative

from collections import deque

visited = {}
def dfs(root):
	stack = deque(root)
	
	while(stack != []):
		n = stack.pop()
		if n != None and not visited[n]:
			f(n)
			visited[n] = True
			
			for neighbor in n.adjacent:
				if not visited[neighbor]:
					stack.append(neighbor)