DSA Graph Traversal

Graph traversal means visiting every node in a graph exactly once by following its edges. Traversal powers map apps, social networks, web crawlers, and puzzle solvers. Two classic methods exist: breadth-first search and depth-first search.

Think of a city with buildings as nodes and roads as edges. A delivery driver wants to visit every building without repeating any. The driver needs a clear plan for which road to take next. BFS and DFS supply two different plans.

Storing a Graph in Code

An adjacency list stores each node with a list of its neighbors.

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

      A
     / \
    B   C
   / \   \
  D   E---F

Breadth-First Search (BFS)

BFS explores the graph level by level. Imagine dropping a pebble into a pond. Ripples spread outward in rings, and nearby points get reached before faraway points.

BFS uses a queue. The oldest waiting node always goes first.

from collections import deque

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

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

Level 0:  A
Level 1:  B  C
Level 2:  D  E  F

Queue changes:
[A] -> [B, C] -> [C, D, E] -> [D, E, F] -> [E, F] -> [F] -> []

BFS finds the shortest path in graphs where every edge has equal length. The first time BFS reaches a node, it arrives by the fewest steps.

Depth-First Search (DFS)

DFS dives down one path as far as possible. At a dead end, it steps back and tries the next branch. A maze explorer follows exactly this habit.

DFS uses a stack, or recursion, which uses the call stack behind the scenes.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

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

Path taken:
A -> B -> D (dead end, back to B)
       B -> E -> F -> C (all visited)

BFS vs DFS

• Data structure: BFS uses a queue, and DFS uses a stack or recursion.
• Order: BFS visits nearby nodes first, and DFS visits deep nodes first.
• Best for: BFS fits shortest paths and level-based tasks. DFS fits maze solving, cycle detection, and exploring all possibilities.
• Memory: BFS stores a wide layer of nodes. DFS stores one long path.

Why the Visited Set Matters

Graphs often contain loops. Without a visited set, the program walks in circles forever. The set records each finished node and blocks repeat visits.

Example: Count Connected Groups

A graph may split into separate islands that share no edges. Running a traversal from every unvisited node counts the islands.

def count_groups(graph):
    visited = set()
    groups = 0
    for node in graph:
        if node not in visited:
            groups += 1
            stack = [node]
            while stack:
                current = stack.pop()
                if current in visited:
                    continue
                visited.add(current)
                for neighbor in graph[current]:
                    stack.append(neighbor)
    return groups

islands = {"A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"], "E": []}
print(count_groups(islands))   # 3

Complexity

• Time: O(V + E), where V counts nodes and E counts edges.
• Space: O(V) for the visited set and the queue or stack.

Real-Life Uses

Social apps suggest friends by exploring the connections of your connections, which is a BFS idea. Web crawlers follow links from page to page and mark each visited page, much like DFS. Puzzle games such as mazes and word ladders search through states with the same two methods. Network tools trace which devices can reach each other through cables and routers.

Common Mistakes

Marking a node as visited too late creates duplicate queue entries. Mark a node the moment you add it to the queue in BFS. Forgetting the visited set in a graph with loops causes endless runs. Trace a small graph on paper and write the queue contents after every step.

Key Points

• Traversal visits each node once by following edges.
• BFS moves level by level with a queue.
• DFS goes deep first with a stack or recursion.
• A visited set prevents endless loops.
• BFS finds shortest paths in unweighted graphs.
• Both methods run in O(V + E) time.