Graphs

Back to DSA & Algorithms/00 - Roadmap Overview

---

What is a Graph?

A graph is a set of vertices (nodes) connected by edges (links). Unlike trees, graphs can have cycles, multiple paths between nodes, and nodes with any number of connections.

Tree:  Strict parent-child, no cycles, one root
Graph: Any node can connect to any other, cycles possible, no single root

Types of Graphs

How to Represent Graphs

java
// 1. Adjacency List (MOST COMMON in interviews)
// Each node maps to its list of neighbors
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", List.of("B", "C"));
graph.put("B", List.of("A", "D"));
graph.put("C", List.of("A"));
graph.put("D", List.of("B"));

// Or building from an edge list:
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
    int u = edge[0], v = edge[1];
    graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
    graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);  // For undirected
}

// 2. Adjacency Matrix
// matrix[i][j] = 1 if edge exists between i and j
int[][] matrix = {
    {0, 1, 1, 0},  // A connects to B, C
    {1, 0, 0, 1},  // B connects to A, D
    {1, 0, 0, 0},  // C connects to A
    {0, 1, 0, 0},  // D connects to B
};

// 3. Edge List
int[][] edges = {{0, 1}, {0, 2}, {1, 3}};

When to Use Which Representation

---

BFS vs DFS: When to Use Which

The Mental Model

BFS: Ripple in a pond — expands outward uniformly from the starting point. DFS: Exploring a maze — go as far as you can, then backtrack.

---

Pattern 1: BFS (Shortest Path in Unweighted Graphs)

What it is

Explore nodes level by level. First all nodes at distance 1, then distance 2, etc. When you first reach a node, that's the shortest path to it.

Template

java
public Map<Integer, Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    visited.add(start);
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    Map<Integer, Integer> distance = new HashMap<>();
    distance.put(start, 0);

    while (!queue.isEmpty()) {
        int node = queue.poll();

        for (int neighbor : graph.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                distance.put(neighbor, distance.get(node) + 1);
                queue.add(neighbor);
            }
        }
    }

    return distance;
}

Multi-Source BFS

Start BFS from multiple sources simultaneously. All sources start in the queue at distance 0.

java
// Rotting Oranges: How long until all fresh oranges rot?
// Multiple rotten oranges spread simultaneously

public int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;

    // Find all rotten oranges (multiple sources)
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) {
                queue.add(new int[]{r, c});
            } else if (grid[r][c] == 1) {
                fresh++;
            }
        }
    }

    if (fresh == 0) return 0;

    int minutes = 0;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    while (!queue.isEmpty()) {
        minutes++;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
    }

    return fresh == 0 ? minutes - 1 : -1;
}

Problems

• 200. Number of Islands - Medium
• 994. Rotting Oranges - Medium
• 286. Walls and Gates - Medium
• 127. Word Ladder - Hard

---

Pattern 2: DFS (Components, Traversal)

Template

java
// Recursive DFS
public void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
    visited.add(node);
    for (int neighbor : graph.getOrDefault(node, List.of())) {
        if (!visited.contains(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}

// Iterative DFS (using explicit stack)
public void dfsIterative(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited.contains(node)) continue;
        visited.add(node);
        for (int neighbor : graph.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
}

Grid as Graph

Many graph problems use a 2D grid. Each cell is a node, and adjacent cells (up/down/left/right) are neighbors.

java
// Number of Islands
public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;

    int rows = grid.length, cols = grid[0].length;
    int count = 0;

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                dfs(grid, r, c, rows, cols);  // Explore entire island
                count++;                       // Found one island
            }
        }
    }

    return count;
}

private void dfs(char[][] grid, int r, int c, int rows, int cols) {
    // Boundary check + water check
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0') return;

    grid[r][c] = '0';  // Mark as visited (sink the island)

    // Explore all 4 neighbors
    dfs(grid, r + 1, c, rows, cols);
    dfs(grid, r - 1, c, rows, cols);
    dfs(grid, r, c + 1, rows, cols);
    dfs(grid, r, c - 1, rows, cols);
}

// Direction array (cleaner for grid traversal):
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for (int[] d : dirs) {
    int nr = r + d[0], nc = c + d[1];
    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
        // process (nr, nc)
    }
}

Clone Graph

java
public Node cloneGraph(Node node) {
    if (node == null) return null;

    Map<Node, Node> cloned = new HashMap<>();  // original node → cloned node
    return dfs(node, cloned);
}

private Node dfs(Node original, Map<Node, Node> cloned) {
    if (cloned.containsKey(original)) return cloned.get(original);

    Node copy = new Node(original.val);
    cloned.put(original, copy);  // Map before recursing (handles cycles)

    for (Node neighbor : original.neighbors) {
        copy.neighbors.add(dfs(neighbor, cloned));
    }

    return copy;
}

// Key: Map original → clone BEFORE recursing into neighbors.
// This handles cycles: if we visit a node again, we return the existing clone.

Problems

• 200. Number of Islands - Medium
• 695. Max Area of Island - Medium
• 133. Clone Graph - Medium
• 417. Pacific Atlantic Water Flow - Medium
• 130. Surrounded Regions - Medium

---

Pattern 3: Topological Sort (Ordering Dependencies)

What it is

Order nodes in a Directed Acyclic Graph (DAG) so that for every edge u→v, u comes before v. Like ordering courses with prerequisites.

The Mental Model

You're getting dressed. Underwear must come before pants, pants before shoes, etc. Topological sort gives you a valid dressing order.

Two Approaches

java
// Approach 1: Kahn's Algorithm (BFS-based, preferred in interviews)
// Start with nodes that have no prerequisites (in-degree = 0)

public List<Integer> topoSortBFS(int n, int[][] edges) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    int[] inDegree = new int[n];

    for (int[] edge : edges) {
        int u = edge[0], v = edge[1];
        graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        inDegree[v]++;
    }

    // Start with all nodes that have no prerequisites
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.add(i);
    }
    List<Integer> order = new ArrayList<>();

    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);

        for (int neighbor : graph.getOrDefault(node, List.of())) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                queue.add(neighbor);  // All prereqs satisfied
            }
        }
    }

    // If we processed all nodes → valid ordering
    // If not → there's a cycle (impossible to order)
    return order.size() == n ? order : new ArrayList<>();
}

// Approach 2: DFS-based (post-order gives reverse topo sort)
public List<Integer> topoSortDFS(int n, int[][] edges) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int[] edge : edges) {
        graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
    }

    Set<Integer> visited = new HashSet<>();
    Set<Integer> inPath = new HashSet<>();   // Nodes in current DFS path (for cycle detection)
    List<Integer> order = new ArrayList<>();
    boolean[] hasCycle = {false};

    for (int i = 0; i < n; i++) {
        if (!visited.contains(i)) {
            dfs(graph, i, visited, inPath, order, hasCycle);
            if (hasCycle[0]) return new ArrayList<>();
        }
    }

    Collections.reverse(order);  // Reverse post-order = topological order
    return order;
}

private void dfs(Map<Integer, List<Integer>> graph, int node,
                 Set<Integer> visited, Set<Integer> inPath,
                 List<Integer> order, boolean[] hasCycle) {
    if (inPath.contains(node)) {
        hasCycle[0] = true;   // Cycle detected!
        return;
    }
    if (visited.contains(node)) return;

    inPath.add(node);
    for (int neighbor : graph.getOrDefault(node, List.of())) {
        dfs(graph, neighbor, visited, inPath, order, hasCycle);
        if (hasCycle[0]) return;
    }
    inPath.remove(node);
    visited.add(node);
    order.add(node);  // Post-order: add AFTER processing all children
}

Course Schedule

java
// Can you finish all courses? (Is there a cycle?)
public boolean canFinish(int numCourses, int[][] prerequisites) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    int[] inDegree = new int[numCourses];

    for (int[] pair : prerequisites) {
        int course = pair[0], prereq = pair[1];
        graph.computeIfAbsent(prereq, k -> new ArrayList<>()).add(course);
        inDegree[course]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) queue.add(i);
    }
    int completed = 0;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        completed++;
        for (int neighbor : graph.getOrDefault(node, List.of())) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                queue.add(neighbor);
            }
        }
    }

    return completed == numCourses;  // All courses completable?
}

Problems

• 207. Course Schedule - Medium
• 210. Course Schedule II - Medium
• 269. Alien Dictionary - Hard

---

Pattern 4: Shortest Path (Weighted Graphs)

Dijkstra's Algorithm

For graphs with non-negative edge weights. Uses a min-heap to always process the closest unvisited node.

java
public int[] dijkstra(Map<Integer, List<int[]>> graph, int start, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.add(new int[]{0, start});  // {distance, node}

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];

        if (d > dist[u]) continue;    // Already found a shorter path to u

        for (int[] edge : graph.getOrDefault(u, List.of())) {
            int v = edge[0], weight = edge[1];
            int newDist = dist[u] + weight;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.add(new int[]{newDist, v});
            }
        }
    }

    return dist;
}

// Why the "if (d > dist[u]) continue" check?
// The heap may contain stale entries. When we find a shorter path to u,
// we push a new entry but don't remove the old one (expensive in a heap).
// So we skip stale entries when we pop them.

// Time: O(E log V) with binary heap
// Space: O(V + E)

Bellman-Ford (Handles Negative Weights)

java
public int[] bellmanFord(int n, int[][] edges, int start) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    // Relax all edges n-1 times
    for (int i = 0; i < n - 1; i++) {
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Check for negative cycles (one more pass)
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
            return null;  // Negative cycle exists!
        }
    }

    return dist;
}

// Time: O(V × E) — slower than Dijkstra but handles negative edges

When to Use Which

Problems

• 743. Network Delay Time - Medium
• 787. Cheapest Flights Within K Stops - Medium
• 1631. Path With Minimum Effort - Medium

---

Pattern 5: Cycle Detection

Directed Graph (Three-Color DFS)

java
// States: 0=unvisited, 1=in current path, 2=fully processed
public boolean hasCycle(List<List<Integer>> graph, int n) {
    int[] state = new int[n];

    for (int i = 0; i < n; i++) {
        if (state[i] == 0 && dfs(graph, i, state)) {
            return true;
        }
    }
    return false;
}

private boolean dfs(List<List<Integer>> graph, int node, int[] state) {
    state[node] = 1;  // Currently processing

    for (int neighbor : graph.get(node)) {
        if (state[neighbor] == 1) return true;    // Back edge → cycle!
        if (state[neighbor] == 0) {
            if (dfs(graph, neighbor, state)) return true;
        }
    }

    state[node] = 2;  // Done processing
    return false;
}

// Why three states?
// State 1 (in path): If we see it again → we've gone in a circle = cycle
// State 2 (done): If we see it → it's been fully explored, no cycle through it
// Just using visited (2 states) doesn't distinguish back edges from cross edges

Undirected Graph

java
// Simpler: just check if we visit a node that isn't our parent
public boolean hasCycleUndirected(List<List<Integer>> graph, int n) {
    boolean[] visited = new boolean[n];

    for (int i = 0; i < n; i++) {
        if (!visited[i] && dfs(graph, i, -1, visited)) {
            return true;
        }
    }
    return false;
}

private boolean dfs(List<List<Integer>> graph, int node, int parent, boolean[] visited) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            if (dfs(graph, neighbor, node, visited)) return true;
        } else if (neighbor != parent) {
            return true;  // Visited + not parent → cycle!
        }
    }
    return false;
}

---

Things You MUST Be Aware Of

1. Visited Set is Critical

java
// Without marking visited, you'll loop forever in cyclic graphs
// or revisit nodes unnecessarily in acyclic ones.
// ALWAYS maintain a visited set/array.

2. Directed vs Undirected Affects Everything

java
// Undirected: add edge BOTH ways
graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);

// Directed: add edge ONE way
graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);

// Cycle detection is DIFFERENT for directed vs undirected

3. Disconnected Graphs

java
// A graph might not be connected! Don't assume you can reach all nodes from any node.
// Always loop through ALL nodes:
for (int i = 0; i < n; i++) {
    if (!visited.contains(i)) {
        dfs(i);
    }
}

4. 0-indexed vs 1-indexed Nodes

java
// Some problems use 0-indexed, some use 1-indexed.
// Always check the problem constraints.
// If 1-indexed: use range [1, n] or allocate arrays of size n+1

---

Decision Guide

Shortest path (unweighted)?
  └── BFS

Shortest path (weighted, no negative)?
  └── Dijkstra

Shortest path (negative weights)?
  └── Bellman-Ford

Connected components?
  └── DFS or BFS or Union-Find

Ordering with dependencies?
  └── Topological Sort (Kahn's BFS)

Cycle detection (directed)?
  └── Three-color DFS or Topo Sort (incomplete = cycle)

Cycle detection (undirected)?
  └── DFS with parent tracking or Union-Find

Grid traversal?
  └── DFS/BFS with direction array and bounds checking