Graphs: Representation & BFS/DFS

This lesson on Graphs: Representation & BFS/DFS is hands-on and example-driven. You will master the foundational mechanics of graph traversals by distinguishing between Breadth-First Search (BFS) and Depth-First Search (DFS). You will learn how to implement both algorithms using queues and stacks, trace their traversal paths, and analyze their generated spanning trees.

What You'll Be Able To Do

• Differentiate between vertex visiting and vertex exploration during graph traversals.
• Implement Breadth-First Search on an adjacency list using a FIFO queue.
• Implement Depth-First Search iteratively with an explicit stack or recursively via the call stack.
• Identify cross edges and construct spanning trees from BFS and DFS traversal paths.
• Map BFS and DFS traversal strategies to tree-equivalent level-order and pre-order traversals.

Detailed Concept Walkthrough

1. Graph Traversal Terminology and Mechanics

Graph traversal relies on a clear distinction between arriving at a node and fully processing its adjacent neighbors.

• Mechanism: Visiting a vertex means landing on that specific node for the first time and marking it as discovered.
• Execution Flow: Exploration occurs when an algorithm iterates through all unvisited neighbors adjacent to the currently active vertex.
• Under the Hood: A tracking mechanism such as a boolean visited array or hash set prevents infinite loops in cyclic graphs during exploration.

# Distinction between visiting a node and exploring its neighbors
visited = set()
def explore_node(graph, u):
    visited.add(u)  # Visiting the vertex
    for v in graph[u]:  # Exploring adjacent neighbors
        if v not in visited:
            print(f"Discovered edge: {u} -> {v}")

Key Takeaway: Visiting touches a single node, while exploration processes all outward connections from that node.

2. Breadth-First Search and Level-by-Level Exploration

Breadth-First Search (BFS) explores outward in concentric rings, exhausting all vertices at distance k before moving to distance k+1.

• Mechanism: BFS enqueues starting vertices into a FIFO queue, systematically popping the oldest node and visiting all its unexplored neighbors before advancing deeper.
• Tree Analogy: BFS operates identically to a level-order traversal on a binary tree, processing sibling nodes before descending to their children.
• Under the Hood: The FIFO queue enforces strict exploration ordering, guaranteeing that nodes are processed in non-decreasing order of their shortest path distance from the root.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        u = queue.popleft()  # Complete exploration of node u
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                queue.append(v)  # Enqueue neighbor for next level

Key Takeaway: BFS completes the full exploration of a current node's neighbors before moving deeper, relying on a FIFO queue.

3. Depth-First Search and Vertex Suspension

Depth-First Search (DFS) dives along a single branch as deeply as possible, suspending exploration of current nodes until it hits a dead end.

• Mechanism: When DFS encounters an unvisited neighbor, it immediately suspends the current vertex's exploration and recursively dives into the neighbor.
• Execution Flow: When a vertex has no remaining unvisited neighbors, the algorithm backtracks to resume exploration of the most recently suspended ancestor.
• Under the Hood: DFS relies on LIFO semantics, using either the program call stack in recursive implementations or an explicit stack data structure.

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        u = stack.pop()  # Access most recently suspended node
        if u not in visited:
            visited.add(u)
            for v in reversed(graph[u]):  # Preserve order onto stack
                if v not in visited:
                    stack.append(v)

Key Takeaway: DFS suspends parent node exploration immediately upon encountering an unvisited child, backtracking via LIFO order.

4. Spanning Trees and Cross Edges

Traversing a connected graph produces a spanning tree of visited edges alongside non-tree edges that link already-visited nodes.

• Mechanism: Traversal edges that discover previously unseen vertices form the branches of a BFS or DFS spanning tree.
• Under the Hood: Cross edges in BFS connect nodes that have already been visited across the same level or between adjacent levels, outside the parent-child tree hierarchy.
• Nuance: Variations in the chosen starting vertex or the order of inspecting adjacent neighbors generate different valid traversal sequences and spanning trees.

# Tracing BFS tree edges vs cross edges
def bfs_tree(graph, start):
    visited = {start}
    queue = deque([start])
    tree_edges, cross_edges = [], []
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                tree_edges.append((u, v))
                queue.append(v)
            elif (v, u) not in tree_edges and (v, u) not in cross_edges:
                cross_edges.append((u, v))
    return tree_edges, cross_edges

Key Takeaway: Graph traversals produce spanning trees, while non-traversal links between previously visited vertices form cross edges.

Topics Covered in Graphs: Representation & BFS/DFS

1. Graph Traversal Terminology (00:23 - 00:37) — The instructor defines the key distinction between visiting an individual node and fully exploring its adjacent neighbors.
2. Conceptual BFS Walkthrough (00:37 - 01:14) — A trace of breadth-first traversal shows level-by-level exploration across a small graph from an arbitrary start node.
3. Conceptual DFS Walkthrough (01:14 - 02:05) — The lesson traces depth-first traversal demonstrating how parent exploration suspends until a dead end forces backtracking.
4. BFS vs DFS Tree Analogies (02:05 - 03:13) — Traversal strategies are compared directly by mapping BFS to level-order and DFS to pre-order binary tree traversals.
5. Queue Implementation of BFS (03:13 - 05:33) — A formal step-by-step walkthrough shows how to manage node exploration order using a FIFO queue.
6. Spanning Trees and Cross Edges (05:33 - 06:33) — The instructor details how BFS creates spanning trees, identifies cross edges, and generates multiple valid sequence variations.
7. Stack Implementation of DFS (06:33 - 07:42) — The formal execution of DFS using a LIFO stack illustrates how suspended parent states and return points are tracked.

DSA for Interviews Cheat Sheet

• collections.deque() — Initializes a double-ended queue for BFS FIFO operations

  queue = deque([start_node])
  

• queue.popleft() — Removes and returns next node to explore in BFS

  curr = queue.popleft()
  

• stack.pop() — Removes top suspended node to backtrack in DFS

  curr = stack.pop()
  

• visited.add(vertex) — Marks vertex as visited to prevent duplicate exploration

  visited.add(neighbor)
  

• BFS Spanning Tree — Sub-graph formed by all primary discovery edges during BFS

  tree_edges.append((parent, child))
  

• Cross Edge — Edge connecting already visited nodes outside spanning tree

  if v in visited: cross_edges.append((u, v))
  

Comparison Table

Common Pitfalls

• Mistake: Marking a node as visited when popping it from a BFS queue instead of when enqueuing. Avoid: Add nodes to the visited set immediately before pushing them into the queue.
• Mistake: Confusing visiting a single vertex with completing exploration of all its neighbors. Avoid: Track node discovery and neighbor loop completion as two distinct algorithmic phases.
• Mistake: Forgetting that varying neighbor iteration orders produces different valid traversal sequences. Avoid: Account for tie-breaking and neighbor insertion order when testing expected paths.

FAQs

• What is the exact distinction between visiting and exploring a vertex? Visiting occurs the moment a traversal algorithm arrives at a node. Exploration is the subsequent process of iterating through and checking all outward edges connected to that node.
• Why does DFS suspend vertex exploration while BFS does not? DFS immediately dives down newly found branches to prioritize maximum depth, suspending parent exploration until reaching a dead end, whereas BFS queues all adjacent neighbors to finish the current level first.
• What creates a cross edge during BFS? A cross edge occurs when an explored vertex encounters an adjacent neighbor that has already been visited through an alternate path in the traversal.
• Can a single graph produce multiple valid BFS or DFS sequences? Yes. Changing the starting vertex or altering the order in which adjacent neighbors are iterated yields different valid traversal paths.