BFS and DFS Graph Traversal — Interactive Learning Simulator

The Story — Two Ways to Search a Building

Traversal means visiting every node of a graph (or tree) one time. A graph is a set of nodes (circles) joined by edges (lines). To traverse it, we need two things: a rule for "which node next?" and a way to remember which nodes we have already seen.

BFS vs DFS at a Glance

Watch Them Race — Animated Diagram

Same tree, same start node 1. Watch the order in which each algorithm lights up the nodes. The small number on each node shows when it was visited.

The Traversal Simulator — Build Your Own Graph

This is your playground. Draw nodes, join them with edges, pick an algorithm, and press Step. Each click runs one line of the algorithm. You will see the queue or stack fill and empty, the current line of code, and a plain-English note of what just happened.

BFS Step by Step — Trace Table

Here is BFS on the sample tree (1 is the root; 2 and 3 are its children; 4, 5 under 2; 6, 7 under 3).

DFS Step by Step (Stack)

Python Implementation

We store the graph as an adjacency list: each node maps to a list of its neighbours.

BFS with a Queue

from collections import deque

graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6, 7],
    4: [2], 5: [2], 6: [3], 7: [3],
}

def bfs(graph, start):
    visited = {start}               # mark when we enqueue
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()      # take from the FRONT
        order.append(node)
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                queue.append(n)     # add to the REAR
    return order

print("BFS:", bfs(graph, 1))

DFS with a Stack

def dfs_stack(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()           # take from the TOP
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for n in reversed(graph[node]):  # so smallest pops first
            if n not in visited:
                stack.append(n)
    return order

print("DFS (stack):", dfs_stack(graph, 1))

DFS with Recursion

def dfs_rec(graph, node, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(node)
    order.append(node)
    for n in graph[node]:
        if n not in visited:
            dfs_rec(graph, n, visited, order)   # go deeper
    return order

print("DFS (recursion):", dfs_rec(graph, 1))

Bonus — BFS Finds the Shortest Path

def shortest_hops(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if n not in dist:
                dist[n] = dist[node] + 1
                queue.append(n)
    return dist

print(shortest_hops(graph, 1))

Queue vs Stack — Side by Side

Time and Space Complexity

V = number of nodes (vertices). E = number of edges.

When to Use Which

Golden Rules