Graphs Pattern

The Graphs pattern models complex networks of vertices (nodes) and edges (relations). It uses Depth-First Search (DFS), Breadth-First Search (BFS), or Disjoint Set Union (DSU) to analyze connectivity, cycles, and dependencies.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem explicitly mentions networks, grids, connections, or node relationships.
• You need to find the shortest path in an unweighted grid or network (BFS).
• You are resolving dependency ordering or prerequisites (Topological Sort / Course Schedule).
• The task requires finding connected regions or checking if a path exists between two nodes.

How It Works

A graph consists of vertices V and edges E. It is represented using an Adjacency List (a map where each node points to a list of its neighbors) or an Adjacency Matrix (a 2D grid).

• DFS: Recursively visit neighbors, marking nodes in a visited set to prevent infinite loops in cyclic graphs.
• BFS: Use a queue to visit nodes level-by-level, tracking shortest paths.
• Union-Find (DSU): Maintain disjoint sets to merge nodes and detect cycles in undirected graphs.

For example, to find if a path exists between start and end:

1. Initialize a visited set: {}.
2. Call DFS starting at start.
3. Mark start as visited.
4. If start == end, return true.
5. For each unvisited neighbor of start, recursively call DFS. If any call returns true, return true.
6. If all paths fail, return false.

Complexity, With Caveats

• Time Complexity: O(V + E) for DFS and BFS, where V is the number of vertices and E is the number of edges. We visit each vertex and edge at most once.
• Space Complexity: O(V + E) to store the adjacency list representation, plus O(V) for the visited set and queue/recursion stack.

Minimal Code Template

import java.util.*;

public class GraphsTemplate {
    // Depth-First Search (DFS) on Adjacency List
    public void dfs(int node, Map<Integer, List<Integer>> adj, Set<Integer> visited) {
        if (visited.contains(node)) return;
        visited.add(node); // mark as visited

        for (int neighbor : adj.getOrDefault(node, new ArrayList<>())) {
            dfs(neighbor, adj, visited);
        }
    }

    // Breadth-First Search (BFS) for Shortest Path
    public int bfs(int start, int target, Map<Integer, List<Integer>> adj) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        queue.offer(start);
        visited.add(start);
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                if (curr == target) return steps;

                for (int neighbor : adj.getOrDefault(curr, new ArrayList<>())) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
            steps++;
        }
        return -1; // target unreachable
    }
}

from collections import deque


# Depth-First Search (DFS) on Adjacency List
def dfs(node: int, adj: dict[int, list[int]], visited: set[int]) -> None:
    if node in visited:
        return
    visited.add(node)  # mark as visited

    for neighbor in adj.get(node, []):
        dfs(neighbor, adj, visited)


# Breadth-First Search (BFS) for Shortest Path
def bfs(start: int, target: int, adj: dict[int, list[int]]) -> int:
    queue = deque([start])
    visited = {start}
    steps = 0

    while queue:
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()
            if curr == target:
                return steps

            for neighbor in adj.get(curr, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        steps += 1

    return -1  # target unreachable

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

class GraphsTemplate {
public:
    // Depth-First Search (DFS)
    void dfs(int node, std::unordered_map<int, std::vector<int>>& adj, std::unordered_set<int>& visited) {
        if (visited.count(node)) return;
        visited.insert(node); // mark as visited

        for (int neighbor : adj[node]) {
            dfs(neighbor, adj, visited);
        }
    }

    // Breadth-First Search (BFS)
    int bfs(int start, int target, std::unordered_map<int, std::vector<int>>& adj) {
        std::queue<int> q;
        std::unordered_set<int> visited;

        q.push(start);
        visited.insert(start);
        int steps = 0;

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int curr = q.front();
                q.pop();
                if (curr == target) return steps;

                for (int neighbor : adj[curr]) {
                    if (!visited.count(neighbor)) {
                        visited.insert(neighbor);
                        q.push(neighbor);
                    }
                }
            }
            steps++;
        }
        return -1;
    }
};

Where This Pattern Falls Short

• Weighted shortest paths: BFS only finds the shortest path on unweighted graphs (where all edges cost 1). If edges have varying weights (e.g. travel times), BFS fails to find the shortest path, and you must use Dijkstra’s Algorithm or Bellman-Ford instead.
• Topological ordering in cyclic graphs: If a directed graph contains a cycle, you cannot compute a topological sort (it is impossible to resolve dependencies). You must detect the cycle first.

Related Patterns, Compared

• Trees: choose this instead when the graph is guaranteed to have no cycles and is connected as a single rooted hierarchy, which simplifies the traversal.
• Tries: choose this specialized sub-pattern when you are storing a dictionary of words character-by-character for fast prefix matches.

Frequently Asked Questions

How do we represent graphs? The most common representations are:

1. Adjacency List: A map of node -> list of neighbors. It uses O(V + E) space and is ideal for sparse graphs.
2. Adjacency Matrix: A 2D array of size V x V where matrix[i][j] = 1 indicates an edge. It uses O(V²) space and is ideal for dense graphs.

What is Topological Sort? Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u comes before v in the ordering. It is used to solve dependency scheduling problems.

What does this pattern test in interviews? It tests your ability to model abstract relationships as graph nodes, handle cyclic loops safely using visited markers, and choose between BFS and DFS.