Python depth-first search
Recursive DFS visits a vertex, then recursively visits each unseen neighbor. The call stack remembers where to resume after a branch finishes.
Python
def dfs(graph, start):
seen = set()
order = []
def visit(node):
if node in seen:
return
seen.add(node)
order.append(node)
for neighbor in graph.get(node, []):
visit(neighbor)
visit(start)
return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": ["A"]}
print(dfs(graph, "A"))
assert dfs({}, "Z") == ["Z"]