search

algorithms §

dfs §

base
visit
visit children

on a tree:

def dfs(root, visit_func):
	if root is None:
		return
	visit_func(root)
	self.pre_order(root.left, visit_func)
	self.pre_order(root.right, visit_func)

on a graph:

def dfs(root, visit_func):
	if root is None:
		return
	visit_func(root)
	root.visit_state = True
	for nb in root.adj_nodes:
		if nb.visit_state == False:
			dfs(nb, visit_func)

on a matrix:

R, C = len(grid), len(grid[0])
visit = set()
def dfs(r, c):
	# base
	visid.add((r, c))
	for dr, dc in [[0, -1], [-1, 0], [0, 1], [1, 0]]:
		nr, nc = r + dr, c + dc
		if (nr in range(R) and nc not in range(C) and (nr, nc) in visit):
			dfs(nr, nc)
	return

bfs §

init q
node = q.popleft()
visit
visit children, add to queue

on a tree:

def bfs(root, visit_func):
	if not root:
		return
	q = deque([root])
	while q:
		node = q.popleft()
		visit_func(node)
		if root.left:
			visit_func(root.left)
		if root.right:
			visit_func(root.left)

on a graph:

def bfs(root):
	if not root: 
		return
	root.visit_state = True
	q = deque([root])
	while q:
		node = q.popleft()
		visit_func(node)
		for nb in root.adj_nodes:
			if nb.visit_state == False:
				nb.visit_state = True
				q.append(nb)

on a matrix:

R, C = len(grid), len(grid[0])
def bfs(r, c):
	visit = set([(r, c)])
	q = deque([(r, c)])
	while q: 
		for _ in range(len(q)):
			r, c, = q.popleft()
				for dr, dc in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
					nr, nc = r + dr, c + dc
					if (
						nr in range(R) and nc in range(C) and
						(nr, nc) not in visit
					):
						# visit 
						visit.add(nr, nc)
						q.append(nr, nc)
						

binary search §