DSA Graph DFS Patterns

Graph DFS patterns are three small jobs built on one depth-first search. Each job reuses the same visited set discipline.

Counting components

Each new start vertex opens one more component. Three starts print below.

def build(n, edges):
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    for v in graph:
        graph[v] = sorted(graph[v])
    return graph

def count_components(graph):
    seen = set()
    count = 0
    for start in sorted(graph):
        if start in seen:
            continue
        count += 1
        stack = [start]
        seen.add(start)
        while stack:
            node = stack.pop()
            for nb in graph[node]:
                if nb not in seen:
                    seen.add(nb)
                    stack.append(nb)
    return count

graph = build(6, [(0, 1), (1, 2), (3, 4)])
print(count_components(graph))

Testing reachability

One search from vertex 0 marks its whole component. Vertex 4 sits outside it.

def build(n, edges):
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    for v in graph:
        graph[v] = sorted(graph[v])
    return graph

def reachable(graph, start, target):
    seen = {start}
    stack = [start]
    while stack:
        node = stack.pop()
        if node == target:
            return True
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb)
                stack.append(nb)
    return False

graph = build(6, [(0, 1), (1, 2), (3, 4)])
print(reachable(graph, 0, 2))
print(reachable(graph, 0, 4))

One visited set for the whole job

The search marks each vertex once. Vertex 3 stays unmarked in this run.

graph = {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: []}
seen = set()
order = []
stack = [0]
seen.add(0)
while stack:
    node = stack.pop()
    order.append(node)
    for nb in sorted(graph[node], reverse=True):
        if nb not in seen:
            seen.add(nb)
            stack.append(nb)
print(order)
print(sorted(seen))

Example

def build(n, edges):
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    for v in graph:
        graph[v] = sorted(graph[v])
    return graph

def census(graph):
    seen = set()
    sizes = []
    visits = 0
    for start in sorted(graph):
        if start in seen:
            continue
        size = 0
        stack = [start]
        seen.add(start)
        while stack:
            node = stack.pop()
            size += 1
            visits += 1
            for nb in graph[node]:
                if nb not in seen:
                    seen.add(nb)
                    stack.append(nb)
        sizes.append(size)
    return sizes, visits

first = build(7, [(0, 1), (1, 2), (2, 0), (3, 4), (5, 6)])
sizes, visits = census(first)
print("Graph one components:", len(sizes))
print("Graph one sizes:", sorted(sizes, reverse=True))
print("Graph one visits:", visits)
second = build(5, [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
sizes, visits = census(second)
print("Graph two components:", len(sizes))
print("Graph two sizes:", sorted(sizes, reverse=True))
print("Graph two visits:", visits)

Key points

Component: a group of vertices that reach each other
Visited set: the set of vertices already claimed by a search
A vertex enters the visited set when the search first reaches it
Counting components means starting one search per unvisited vertex
A reachability test returns true when one search marks the target
One shared visited set keeps the total visits equal to the vertex count

In this example, a census runs depth-first searches over two graphs. Graph one holds three components with sizes three, two and two. The sizes print largest first. Graph two forms one ring, so it holds one component of size five. Each census visits every vertex exactly once. The visit counts print seven and five, matching the vertex counts.

Note

A fresh visited set per start would recount the same vertices.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

def build(n, edges):
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    for v in graph:
        graph[v] = sorted(graph[v])
    return graph

def census(graph):
    seen = set()
    sizes = []
    visits = 0
    for start in sorted(graph):
        if start in seen:
            continue
        size = 0
        stack = [start]
        seen.add(start)
        while stack:
            node = stack.pop()
            size += 1
            visits += 1
            for nb in graph[node]:
                if nb not in seen:
                    seen.add(nb)
                    stack.append(nb)
        sizes.append(size)
    return sizes, visits

first = build(7, [(0, 1), (1, 2), (2, 0), (3, 4), (5, 6)])
sizes, visits = census(first)
print("Graph one components:", len(sizes))
print("Graph one sizes:", sorted(sizes, reverse=True))
print("Graph one visits:", visits)
second = build(5, [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
sizes, visits = census(second)
print("Graph two components:", len(sizes))
print("Graph two sizes:", sorted(sizes, reverse=True))
print("Graph two visits:", visits)

Exercise

A DFS census of a graph starts a new search 4 times. How many components does the graph have?

One component Two components Four components It cannot be known