Prog Prep

BFS

Denote

: the graph

: the tree

: the set of nodes already in

: a queue of nodes to check next for target


def BFS(G, rootm target):
		S.add(root)
		T.add(root, None)
		Q = [root]
		while Q:
				cur = Q.pop(0)
				if cur is target:
						return cur parent list
				for v in G[cur]:
						if v not in S:
								S.add(v)
								T.add(v, cur)
								Q += [v]

DFS

: the set of all visited nodes, initially empty

: the tree of visited nodes, form some root


def DFS(G, cur, parent):
		if cur not in S:
				S.add(cur)
				T.add(cur, parent)
				for v in G[cur]:
						DFS(G, v, cur)