Graphs — Recap

A graph consists of vertices (nodes) connected by edges. Graphs can be directed or undirected, weighted or unweighted. Graph traversal algorithms visit every vertex systematically. The two fundamental approaches are BFS (Breadth-First Search) and DFS (Depth-First Search).

Example graph (undirected) used throughout this lesson:

A - B - D
|   |
C - E

Adjacency list: A:[B,C], B:[A,D,E], C:[A,E], D:[B], E:[B,C]

Breadth-First Search (BFS)

BFS explores a graph level by level — first all neighbours of the start node, then their neighbours, and so on. It uses a FIFO queue and a visited set to avoid revisiting nodes.

Algorithm

function BFS(graph, start)
    queue ← [start]
    visited ← {start}
    order ← []
    while queue is not empty
        node ← dequeue(queue)    // take from front (FIFO)
        order.append(node)
        for neighbour in graph[node]
            if neighbour not in visited then
                visited.add(neighbour)
                enqueue(queue, neighbour)
            endif
        next neighbour
    endwhile
    return order
endfunction

Worked Trace — BFS from A

BFS order: A → B → C → D → E

Complexity: O(V + E) where V = vertices, E = edges. Every vertex and edge is processed exactly once.

BFS Applications

• Shortest path (unweighted): BFS guarantees the fewest edges between source and any node it visits first — used in GPS routing for unweighted graphs, social network "degrees of connection".
• Web crawlers: start from a page, explore all links at depth 1 first, then depth 2, etc.
• Peer-to-peer networks: finding all nodes within k hops.
• Garbage collection: finding all reachable objects from roots.

Depth-First Search (DFS)

DFS explores a graph by going as deep as possible along each branch before backtracking. It uses a LIFO stack (or the call stack for recursion) and a visited set.

Algorithm (Iterative — uses explicit stack)

function DFS_iterative(graph, start)
    stack ← [start]
    visited ← {}
    order ← []
    while stack is not empty
        node ← pop(stack)        // take from top (LIFO)
        if node not in visited then
            visited.add(node)
            order.append(node)
            for neighbour in graph[node]
                if neighbour not in visited then
                    push(stack, neighbour)
                endif
            next neighbour
        endif
    endwhile
    return order
endfunction

Algorithm (Recursive — uses call stack)

function DFS_recursive(graph, node, visited)
    if visited is None then visited ← {}
    visited.add(node)
    process(node)
    for neighbour in graph[node]
        if neighbour not in visited then
            DFS_recursive(graph, neighbour, visited)
        endif
    next neighbour
endfunction

Worked Trace — DFS from A (iterative)

DFS order (one possible): A → C → E → B → D (order depends on neighbour ordering)

Complexity: O(V + E) — same as BFS. Every vertex and edge is processed exactly once.

DFS Applications

• Topological sort: ordering of tasks where some must precede others (dependency resolution, build systems).
• Cycle detection: check if a graph contains a cycle — if DFS revisits a node already in the current path, a cycle exists.
• Maze solving: DFS explores one path fully before backtracking to try another.
• Finding connected components: run DFS from unvisited nodes to identify all components.

BFS vs DFS Comparison