Introduction to Graphs

A graph is a non-linear data structure defined by a set of vertices (nodes) and a set of edges (connections between nodes). Graphs can model many real-world systems like social networks, road maps, or maze grids.

Types of graphs include:

• Directed Graphs (Digraphs): Edges have a direction (e.g., one-way streets).
• Undirected Graphs: Edges are bidirectional links.
• Weighted Graphs: Edges carry a cost or weight. Unweighted graphs assume all edges have equal weight (often 1).
• Cyclic vs. Acyclic Graphs: Cyclic graphs contain cycles (paths starting and ending at the same node). Acyclic graphs do not. A Directed Acyclic Graph (DAG) is a common type.

In coding interviews, graph problems are common for relationship or connectivity tasks. Keywords hinting at graph solutions include “neighbors,” “connected to,” “network,” “grid” (grids can be graphs), “paths,” or requests to “traverse” or “search.”

Core Idea / Mental Model

A graph can be thought of as points connected by lines, like a city map. Two fundamental ways to explore graphs are Breadth-First Search (BFS) and Depth-First Search (DFS).

BFS: Explores level by level, like ripples. Visits immediate neighbors, then neighbors' neighbors. Uses a queue (FIFO). Ensures closest nodes are visited first. Useful for shortest path in unweighted graphs.

DFS: Explores along a path as far as possible before backtracking, like following one road to its end. Uses a stack (implicitly via recursion or explicitly). Useful for topological sort, cycle detection, and puzzle solving.

Both BFS and DFS require marking visited nodes to avoid infinite loops in cyclic graphs.

Graph Representation & Traversals (Python)

a. Graph Representation (Adjacency List & Matrix)

Graphs are typically represented using an adjacency list (good for sparse graphs) or an adjacency matrix (good for dense graphs).

def build_adj_list(num_vertices, edges, directed=False):
    adj = [[] for _ in range(num_vertices)]
    for (u, v) in edges:
        adj[u].append(v)
        if not directed: adj[v].append(u)
    return adj

def build_adj_matrix(num_vertices, edges, directed=False):
    matrix = [[0] * num_vertices for _ in range(num_vertices)]
    for (u, v) in edges:
        matrix[u][v] = 1
        if not directed: matrix[v][u] = 1
    return matrix

# V = 5; edge_list = [(0,1),(0,2),(1,2),(2,3),(2,4)] (Undirected)
# adj_list = build_adj_list(V, edge_list)
# adj_matrix = build_adj_matrix(V, edge_list)

For weighted graphs, store (neighbor, weight) pairs in lists or weights in the matrix.

b. BFS and DFS Traversals

Breadth-First Search (BFS) – Iterative

from collections import deque
def bfs_traverse(adj, start_node):
    visited = set([start_node])
    order = []
    queue = deque([start_node])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order
# bfs_traverse(adj_list, 0) -> e.g., [0, 1, 2, 3, 4]

Depth-First Search (DFS) – Recursive

def dfs_recursive_util(adj, node, visited, order):
    visited.add(node)
    order.append(node)
    for neighbor in adj[node]:
        if neighbor not in visited:
            dfs_recursive_util(adj, neighbor, visited, order)

def dfs_recursive_traverse(adj, start_node):
    visited = set()
    order = []
    dfs_recursive_util(adj, start_node, visited, order)
    return order
# dfs_recursive_traverse(adj_list, 0) -> e.g., [0, 1, 2, 3, 4]

Depth-First Search (DFS) – Iterative

def dfs_iterative_traverse(adj, start_node):
    visited = set() # To track visited nodes overall
    order = []
    stack = [start_node]
    while stack:
        node = stack.pop()
        if node not in visited: # Process node only if not visited
            visited.add(node)
            order.append(node)
            # Add unvisited neighbors to stack (reverse for specific order)
            for neighbor in reversed(adj[node]): # Process left children first
                if neighbor not in visited:
                     stack.append(neighbor)
    return order
# dfs_iterative_traverse(adj_list, 0)

c. Cycle Detection

Directed Graph Cycle Detection (DFS)

def has_cycle_directed(num_vertices, edges):
    adj = build_adj_list(num_vertices, edges, directed=True)
    visited = [False] * num_vertices
    recursion_stack = [False] * num_vertices

    def dfs_cycle_check(u):
        visited[u] = True
        recursion_stack[u] = True
        for v in adj[u]:
            if not visited[v]:
                if dfs_cycle_check(v): return True
            elif recursion_stack[v]:
                return True # Cycle detected
        recursion_stack[u] = False
        return False

    for i in range(num_vertices):
        if not visited[i]:
            if dfs_cycle_check(i): return True
    return False
# has_cycle_directed(4, [(0,1),(0,2),(1,2),(2,0),(2,3)]) -> True

Undirected Graph Cycle Detection (DFS)

def has_cycle_undirected(num_vertices, edges):
    adj = build_adj_list(num_vertices, edges, directed=False)
    visited = [False] * num_vertices

    def dfs_cycle_check(u, parent):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                if dfs_cycle_check(v, u): return True
            elif v != parent:
                return True # Cycle detected
        return False

    for i in range(num_vertices):
        if not visited[i]:
            if dfs_cycle_check(i, -1): return True # Start with no parent
    return False
# has_cycle_undirected(4, [(0,1),(0,2),(1,2),(2,3)]) -> True

Interactive Animation (BFS Traversal)

The animation below demonstrates Breadth-First Search (BFS) on a sample graph. BFS explores nodes level by level, starting from a source node. Watch how the queue is used and nodes are visited.

1. Initial state: Queue = [start_node], Visited = {start_node}.
2. Dequeue a node, add to traversal order.
3. Enqueue its unvisited neighbors, mark them visited.
4. Repeat until queue is empty.

Time & Space Complexity

Graph Representation:
- Adjacency List: Time O(V+E) to build, Space O(V+E).
- Adjacency Matrix: Time O(V²) to build, Space O(V²).

BFS Traversal: Time O(V+E) with adj list. Space O(V) for visited set and queue.

DFS Traversal: Time O(V+E) with adj list. Space O(V) for visited set and recursion stack (or explicit stack).

Cycle Detection (DFS-based): Time O(V+E). Space O(V) for visited arrays and recursion stack.

Common Pitfalls

• Off-by-One and Indexing Errors: Especially with 0-indexed vs 1-indexed nodes.
• Infinite Loops/Recursion: Forgetting to mark nodes visited or incorrect visited logic.
• Incorrect Base/Edge Conditions: Handling empty graphs, isolated nodes.
• Not Traversing All Components: For disconnected graphs, ensure all parts are visited.
• Visited-State Mismanagement: Crucial for cycle detection (e.g., `recursion_stack` in directed, `parent` in undirected).
• Queue/Stack Usage Errors: Pushing visited nodes, wrong pop order.
• Mutable Default Arguments (Python): Use `None` for default list/set arguments in recursive functions.

Test with simple examples and edge cases to ensure correctness.