Graph

Graph Problems

Graph problems are very common in coding interviews. The main focus areas include graph construction, graph traversal (BFS/DFS), path search, connectivity checks, and Union-Find (Disjoint Set Union, DSU). Below is a comprehensive summary.

1. How to Build a Graph (Adjacency List)

The most common representation is the Adjacency List.

In Python, we usually use collections.defaultdict(list):

1
2
3
4
5
6
7
8
9
import collections

graphs = collections.defaultdict(list)

# edges is a list of pairs, e.g., [[0,1],[0,2],[1,2]]
for edge in edges:
    start, end = edge
    graphs[start].append(end)
    graphs[end].append(start)  # For undirected graphs, add both directions

Now, graphs[node] gives all neighbors of a node.

2. How to Traverse a Graph

BFS is typically used for shortest paths or level-order traversal.

Python BFS template:

1
2
3
4
5
6
7
8
9
10
11
queue = collections.deque([start])
visited = {start}

while queue:
    size = len(queue)
    for _ in range(size):
        curr = queue.popleft()
        for neighbor in graphs.get(curr, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

DFS is useful for path enumeration, connected components, or topological sorting.

Java DFS template for path search:

1
2
3
4
5
6
7
8
9
10
11
12
public void dfs(List<Integer> path, int curr, int target, 
                List<List<Integer>> result, int[][] graph) {
    if (curr == target) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int node : graph[curr]) {
        path.add(node);
        dfs(path, node, target, result, graph);
        path.remove(path.size() - 1); // backtracking
    }
}

3. Classic Problems

261. Graph Valid Tree

Description: Check if an undirected graph is a valid tree. Conditions:

  1. No cycles
  2. Connected

Approach:

  • BFS/DFS to detect cycles
  • Or Union-Find to detect cycles
  • Finally, check connectivity

127. Word Ladder

Description: Given a dictionary, transform beginWord into endWord one letter at a time. Find the shortest transformation sequence length.

Approach:

  • BFS, where each layer represents one transformation
  • For each word, replace every character with a-z and check if it’s in the dictionary

133. Clone Graph

Description: Clone an undirected connected graph.

Approach:

  • BFS or DFS
  • Use a hash map to map old nodes → new nodes

797. All Paths From Source to Target

Description: In a DAG, find all paths from node 0 to n-1.

Approach:

  • DFS + backtracking
  • Save the path when target is reached

269. Alien Dictionary

Description: Given a sorted list of words in an alien language, derive the letter order.

Approach:

  • Compare adjacent words to extract precedence relations (directed edges)
  • Topological sort to find the order

332. Reconstruct Itinerary

Description: Given airline tickets [from, to], reconstruct the itinerary with smallest lexical order.

Approach:

  • Hierholzer’s Algorithm for Eulerian path
  • DFS with priority queue (lexical order)

547. Number of Provinces

Description: Given a connectivity matrix, find the number of provinces (connected components).

Approach:

  • BFS/DFS traversal
  • Or Union-Find

863. All Nodes Distance K in Binary Tree

Description: Return all nodes that are exactly distance K from the target node.

Approach:

  • Treat the tree as a graph (connect parent and child both ways)
  • BFS from target until reaching level K

323. Number of Connected Components in an Undirected Graph

Description: Count the number of connected components in an undirected graph.

Approach:

  • BFS/DFS
  • Or Union-Find (merge nodes in same component, count roots at the end)

4. Templates

BFS Template (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import deque, defaultdict

def bfs(start, edges):
    graphs = defaultdict(list)
    for u, v in edges:
        graphs[u].append(v)
        graphs[v].append(u)

    visited = {start}
    queue = deque([start])

    while queue:
        curr = queue.popleft()
        for neighbor in graphs[curr]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

DFS Template (Java)

1
2
3
4
5
6
7
8
9
10
11
12
public void dfs(List<Integer> path, int curr, int target, 
                List<List<Integer>> result, int[][] graph) {
    if (curr == target) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int node : graph[curr]) {
        path.add(node);
        dfs(path, node, target, result, graph);
        path.remove(path.size() - 1); // backtracking
    }
}

5. Key Takeaways

  • Graph construction → adjacency list
  • Traversal → BFS (shortest path, level order), DFS (paths, connectivity)
  • Union-Find → cycle detection, connected components
  • Common interview patterns:
    • Valid Tree
    • Word Ladder (BFS shortest transformation)
    • Clone Graph (graph copy)
    • All Paths (DFS backtracking)
    • Alien Dictionary (topological sort)
    • Reconstruct Itinerary (Eulerian path)
    • Provinces / Connected Components (DFS/UF)
    • Distance K in Binary Tree (tree as graph)