🎓 A1Learner
🔍
0 of 47 lessons completed

Traversing a Graph

Graph traversal is a walk that visits every reachable node in a graph in a chosen order. The walk follows edges from a start node until no new node can be reached.

Recognition signal

A problem asks for a graph traversal when it asks to visit every reachable node. The input is nodes joined by edges, and the order of visits is part of the answer.

signals = [
    "Visit every reachable node.",
    "Nodes are joined by edges.",
    "Order of visits matters."
]
for line in signals:
    print(line)

Template: breadth-first walk

Breadth-first search uses a queue and a visited set. Nodes leave the queue in level order, and each new neighbor is marked visited at once.

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": []
}

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order

print(bfs(graph, "A"))

Worked problem: depth-first walk

Depth-first search follows one branch to its end before trying the next branch. The same visited set rule keeps the walk from repeating a node.

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": []
}

def dfs(graph, node, seen, order):
    seen.add(node)
    order.append(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(graph, nxt, seen, order)
    return order

print(dfs(graph, "A", set(), []))

Example

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
    "G": []
}

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order

order = bfs(graph, "A")
print(order)
print("Reachable:", len(order))

Key points

  • Graph: a set of nodes joined by edges.
  • Visited set: a record of nodes already seen, so no node is visited twice.
  • Use breadth-first search to visit nodes level by level from the start.
  • Use depth-first search to follow one branch as far as it goes before backtracking.

The graph has seven nodes, but G has no edge to the rest. The walk starts at A and follows edges level by level. It reaches six nodes, so G is never visited and the count is 6.

Note

mark a node as visited when it is first seen, not when it is finished.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Which walk visits nodes level by level from the start?