Python Graphs and Graph Traversal

Decide what vertices and edges mean before writing code: here, vertices are trail junctions and an edge means a walkable trail between two junctions.

• Undirected edges work both ways, so each one appears in both vertices' lists, as in trails above.
• Directed edges go one way, like a one-way boardwalk: "Pond": ["Woods"] without "Woods": ["Pond"].
• Weighted edges carry a cost, such as distance: {"Gate": {"Pond": 1.2, "Hill": 0.8}}.

from collections import defaultdict
edges = [("Gate", "Pond"), ("Gate", "Hill"), ("Pond", "Woods"), ("Hill", "Woods")]
graph = defaultdict(list)
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)          # omit this line for a directed graph

An adjacency list uses memory proportional to vertices plus edges and lets you loop over a vertex's neighbours quickly, which is what traversals need. An adjacency matrix, an n × n grid of 0s and 1s, answers "is there an edge between A and B?" in O(1) but uses n² memory, so it suits small or dense graphs.

In a graph with cycles, a traversal that simply follows edges would loop forever: Gate → Pond → Gate → Pond... Every traversal therefore keeps a visited set and skips vertices it has already seen:

seen = {"Gate"}
for neighbor in trails["Gate"]:
    if neighbor not in seen:
        seen.add(neighbor)
        # schedule neighbor for exploration

A set gives O(1) average membership checks, so the whole traversal runs in O(V + E) time: each vertex is processed once and each edge examined a constant number of times.

When you mark a vertex matters. In BFS, mark it as seen when you add it to the queue, not when you take it out. Marking late lets the same vertex be queued several times by different neighbours, wasting work and, in BFS, potentially recording the wrong distance. Disconnected vertices are never reached from the start vertex at all; to visit every part of a graph, start a new traversal from each vertex not yet seen.

BFS explores outward in rings: first the start vertex, then everything one edge away, then everything two edges away, and so on. It uses a queue:

from collections import deque

def hops_from(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return distance

Because BFS reaches vertices in order of distance, the first time it finds a vertex is via a route with the fewest edges. That makes it the algorithm for shortest paths in unweighted graphs, such as "fewest trail junctions between the gate and the woods". Recording each vertex's predecessor lets you reconstruct the route.

BFS doesn't find the shortest distance when edges have different lengths; a route with fewer but longer trails may be counted as shorter. Weighted shortest paths need Dijkstra's algorithm, which replaces the queue with a priority queue (heapq).

DFS follows one branch as far as it can before backing up and trying alternatives. It uses a stack, either explicitly or through recursion:

def dfs(graph, start):
    order, seen, stack = [], set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex in seen:
            continue
        seen.add(vertex)
        order.append(vertex)
        for neighbor in reversed(graph[vertex]):   # visit in listed order
            if neighbor not in seen:
                stack.append(neighbor)
    return order

DFS is the basis for finding connected components, detecting cycles, topological sorting of tasks with dependencies, and solving mazes and puzzles. It doesn't find shortest paths.

The visiting order depends on the order neighbours are listed; change the adjacency list order and DFS (and BFS) visit vertices in a different sequence, though they reach the same set of vertices. A recursive DFS is shorter to write but limited by Python's recursion depth on long paths, so the explicit stack version is safer for large graphs.

Task: implement BFS and DFS for a trail graph with a cycle and a disconnected vertex.

from collections import deque

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

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

def dfs(start, seen=None):
    seen = seen if seen is not None else []
    seen.append(start)
    for n in graph[start]:
        if n not in seen:
            dfs(n, seen)
    return seen

print(bfs("A"))   # ['A', 'B', 'C', 'D']
print(dfs("A"))   # ['A', 'B', 'D', 'C']
print(bfs("E"))   # ['E']: the disconnected vertex is never reached from A

The cycle A–B–D–C–A doesn't cause an infinite loop because both traversals skip seen vertices. For the worked check, the traversal that finds shortest hop counts in an unweighted graph is breadth-first search.

The NetworkX documentation covers graph algorithms in depth, and Python's graphlib module provides topological sorting. Continue with recursive problem solving. Practise with the Python exercises and Python quiz.