Graphs: A Refresher

Graphs are one of the most versatile and commonly tested data structures in technical interviews. Whether you’re a new engineer or brushing up for an interview, understanding graphs and their algorithms is crucial. This guide will cover the fundamentals, common types of graphs, traversal techniques, and essential problems to practice.

What Is a Graph?

A graph is a collection of nodes (vertices) connected by edges. It can be used to model networks, social connections, maps, and much more.

Key Terminology:

• Vertex (Node): A single entity in the graph.

• Edge: A connection between two nodes.

• Adjacency: Two nodes are adjacent if they are connected by an edge.

• Weighted Graph: Edges have weights (values) representing cost, distance, etc.

• Directed vs. Undirected Graph:

  • Directed: Edges have a direction (A → B).

  • Undirected: Edges don’t have direction (A — B).

• Cyclic vs. Acyclic Graph:

  • Cyclic: Contains at least one cycle.

  • Acyclic: No cycles (e.g., Directed Acyclic Graph (DAG)).

• Connected vs. Disconnected Graph:

  • Connected: There’s a path between every pair of nodes.

  • Disconnected: Some nodes are isolated.

Graph Representation:

Graphs are typically represented in two ways:

Adjacency List (Efficient for sparse graphs)

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

• Space Complexity: O(V + E)

• Best for most real-world applications.

Adjacency Matrix (Efficient for dense graphs)

# Adjacency Matrix for 4 nodes (A, B, C, D)
graph = [
    [0, 1, 1, 0],  # A → B, C
    [1, 0, 0, 1],  # B → A, D
    [1, 0, 0, 1],  # C → A, D
    [0, 1, 1, 0]   # D → B, C
]

• Space Complexity: O(V²)

• Best for small, dense graphs.

Graph Traversal Techniques

Depth-First Search (DFS)

DFS explores as deep as possible before backtracking. It can be implemented recursively or iteratively using a stack.

Recursive DFS Example:

def dfs(graph, node, visited=set()):
    if node not in visited:
        print(node, end=" ")
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

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

dfs(graph, 'A')  # Output: A B D E F C

• Time Complexity: O(V + E)

Breadth-First Search (BFS)

BFS explores all neighbors at the current depth before moving deeper. It uses a queue.

Iterative BFS Example:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            queue.extend(graph[node])

bfs(graph, 'A')  # Output: A B C D E F

• Time Complexity: O(V + E)

Common Graph Algorithms

Topological Sorting (for Directed Acyclic Graphs - DAGs)

Used in task scheduling, dependency resolution, and course prerequisites.Two common approaches:

1. Kahn’s Algorithm (BFS-based)

2. DFS-Based Topological Sorting

Example:

from collections import deque

def topological_sort(graph, num_nodes):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([node for node in in_degree if in_degree[node] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_nodes else "Cycle detected"

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

print(topological_sort(graph, 6))  # Output: ['A', 'B', 'C', 'D', 'E', 'F']

• Time Complexity: O(V + E)

Shortest Path Algorithms

Dijkstra’s Algorithm 🚀 (Single Source, Non-Negative Weights)

• Uses a priority queue (min-heap).

• Time Complexity: O((V + E) log V)

Bellman-Ford Algorithm (Single Source, Handles Negative Weights)

• Time Complexity: O(VE)

Floyd-Warshall Algorithm (All-Pairs Shortest Path)

• Time Complexity: O(V³)

Cycle Detection in Graphs

• Undirected Graph: Use DFS with a parent pointer.

• Directed Graph: Use DFS + recursion stack or Kahn’s Algorithm (for DAG detection).

Essential Graph Problems for Interviews

Easy:

✅ Find if a Path Exists in a Graph (LeetCode #1971)

✅ Number of Provinces (LeetCode #547)

✅ Flood Fill (LeetCode #733)

Medium:

✅ Course Schedule (LeetCode #207)

✅ Pacific Atlantic Water Flow (LeetCode #417)

✅ Rotting Oranges (LeetCode #994)

Hard:

✅ Shortest Path in a Grid with Obstacles (LeetCode #1293)

✅ Word Ladder (LeetCode #127)

✅ Minimum Cost to Connect All Points (LeetCode #1584)

Final Tips for Interviews

Know BFS vs. DFS: Use BFS for shortest paths and DFS for deeper explorations.

Practice Different Graph Representations: Learn when to use adjacency lists vs. matrices.

Understand Common Graph Problems: Especially shortest paths, cycle detection, and connected components.

Closing Thoughts

Graphs appear in many real-world applications, from networking to recommendation systems. Mastering these algorithms will significantly boost your problem-solving skills for coding interviews. Happy coding!