DSA Graph Traversal

Why Traverse a Graph?

Traversal means systematically visiting every vertex reachable from a starting point, exactly once, so you can search for a target, list connected components, or explore the graph's structure. Because graphs can contain cycles, every traversal algorithm must track which vertices have already been visited, or it can loop forever.

Breadth-First Search (BFS)

BFS explores a graph level by level: it visits the start vertex, then all of its direct neighbors, then all of their unvisited neighbors, and so on outward. It uses a queue (first-in, first-out) to decide which vertex to expand next. Because it expands outward one layer at a time, BFS is the standard choice for finding the shortest path measured in number of edges within an unweighted graph.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        vertex = queue.popleft()
        order.append(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

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

print(bfs(graph, "A"))  # ['A', 'B', 'C', 'D', 'E']

Depth-First Search (DFS)

DFS explores as far as possible down one branch before backtracking, using a stack (last-in, first-out) instead of a queue. It can be written recursively, where the function call stack plays the role of the stack, or iteratively with an explicit stack. DFS fits naturally with tasks like detecting cycles, finding connected components, and topological sorting.

def dfs_recursive(graph, vertex, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []

    visited.add(vertex)
    order.append(vertex)

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)

    return order

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

print(dfs_recursive(graph, "A"))  # ['A', 'B', 'D', 'C', 'E']

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)
        for neighbor in reversed(graph[vertex]):
            if neighbor not in visited:
                stack.append(neighbor)

    return order

print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'C', 'E']

• Shortest path by edge count in an unweighted graph: use BFS.
• Exploring deep structures with limited memory for the frontier, such as maze solving: use DFS.
• Detecting cycles or finding connected components: either works; DFS is often simpler to write recursively.
• Topological sorting of a directed acyclic graph: use DFS.
• Finding all vertices within a fixed number of hops of a start vertex: use BFS.