Returns a DFS tree, formed by a set of parent pointers for verties reachable from $s$ in the order the search discovered them
def dfs(Adj, s, parent=None, order=None):
if parent is None:
parent = [None for v in Adj]
parent[s] = s
order = []
for next in Adj[s]:
if parent[next] is None:
# iteration happens here
parent[next] = s
dfs(Adj, next, parent, order)
order.append(s)
return parent, order
(From pset 6.1.1) An iteration of DFS can be thought of as when we call DFS on an unexplored vertex, or when we update the parent list
def graph_explore(Adj):
parent = [None for v in Adj]
order = []
for v in range(len(Adj)):
if parent[v] is None:
parent[v] = v # root
dfs(Adj, v, parent, order) # DFS from v (BFS can also be used)
return parent, order
parent[b] = a
); $b$ discovered after $a$ and both haven't finished yetNot a tree edge
Facts from exercises