🎓 A1Learner
🔍

DSA Depth-First Search on Graphs

Depth-first search is a graph walk that follows one path as far as it goes before stepping back. A visited set records the vertices already seen, so circles in the graph cannot trap the walk.

Recursive DFS

The function visits a vertex, then calls itself on each unvisited neighbour. The order below follows one path at a time.

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"), ("C", "F")]
graph = {}
for a, b in edges:
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
for name in graph:
    graph[name] = sorted(graph[name])
visited = set()
order = []
def dfs(v):
    visited.add(v)
    order.append(v)
    for nxt in graph[v]:
        if nxt not in visited:
            dfs(nxt)
dfs("A")
print(order)

DFS with an explicit stack

A stack holds the vertices waiting for a visit. Neighbours are pushed in reverse order, so the smallest is popped first.

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"), ("C", "F")]
graph = {}
for a, b in edges:
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
for name in graph:
    graph[name] = sorted(graph[name])
visited = set()
order = []
stack = ["A"]
while stack:
    v = stack.pop()
    if v in visited:
        continue
    visited.add(v)
    order.append(v)
    for nxt in reversed(graph[v]):
        if nxt not in visited:
            stack.append(nxt)
print(order)

Example

edges = [
    ("A", "B"), ("A", "C"), ("B", "D"),
    ("B", "E"), ("C", "F"), ("D", "G"),
]
graph = {}
for a, b in edges:
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
for name in graph:
    graph[name] = sorted(graph[name])

visited = set()
recursive_order = []

def dfs(v):
    visited.add(v)
    recursive_order.append(v)
    for nxt in graph[v]:
        if nxt not in visited:
            dfs(nxt)

dfs("A")
print("Recursive:", recursive_order)

seen = set()
stack_order = []
stack = ["A"]
while stack:
    v = stack.pop()
    if v in seen:
        continue
    seen.add(v)
    stack_order.append(v)
    for nxt in reversed(graph[v]):
        if nxt not in seen:
            stack.append(nxt)
print("Stack:", stack_order)
print("Vertices visited:", len(seen))

Key points

  • Depth-first search: a walk that follows one path to its end before stepping back
  • Visited set: a set that records the vertices the walk has already seen
  • Use a visited set to stop the walk from circling forever
  • The recursive form stores its path in the call stack
  • The stack form stores its path in an explicit stack
  • The visit order depends on the order neighbours are tried.

In this example, both forms of DFS walk the same graph from A. The recursive form dives from A to B to D to G first. G has no unvisited neighbours, so the walk steps back and takes E next. Only then does it cross to C and F. The stack form pushes neighbours in reverse sorted order. That makes it pop the same neighbour the recursion would call first. Both orders match, and the visited count shows all seven vertices were seen once.

Note

These lessons always try neighbours in sorted order.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Why does DFS on a graph keep a visited set?