Graphs

A graph consists of vertices (nodes) and edges. Can be directed/undirected, weighted/unweighted, cyclic/acyclic. Representations: adjacency list (space-efficient, O(V+E)) or adjacency matrix (O(V²), fast lookup). Key algorithms: BFS (shortest path in unweighted), DFS (cycle detection, topological sort), Dijkstra (shortest path weighted), Topological Sort (DAG ordering), Union-Find (connected components).

Key Concepts

Deep Dive: Graph Representation

// Adjacency list (most common)
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.computeIfAbsent(0, k -> new ArrayList<>()).add(1);
graph.computeIfAbsent(1, k -> new ArrayList<>()).add(2);

// Or with array of lists
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(0).add(1);  // edge 0 → 1

Deep Dive: BFS & DFS

BFS (shortest path in unweighted graph):

public int bfs(Map<Integer, List<Integer>> graph, int start, int end) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    queue.offer(start);
    visited.add(start);
    int level = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int node = queue.poll();
            if (node == end) return level;
            for (int neighbor : graph.getOrDefault(node, List.of())) {
                if (visited.add(neighbor)) queue.offer(neighbor);
            }
        }
        level++;
    }
    return -1;
}

DFS (cycle detection in directed graph):

// 0 = unvisited, 1 = in progress, 2 = done
public boolean hasCycle(Map<Integer, List<Integer>> graph, int n) {
    int[] state = new int[n];
    for (int i = 0; i < n; i++) {
        if (dfs(graph, i, state)) return true;
    }
    return false;
}
private boolean dfs(Map<Integer, List<Integer>> graph, int node, int[] state) {
    if (state[node] == 1) return true;  // Cycle!
    if (state[node] == 2) return false;
    state[node] = 1;
    for (int neighbor : graph.getOrDefault(node, List.of())) {
        if (dfs(graph, neighbor, state)) return true;
    }
    state[node] = 2;
    return false;
}

Deep Dive: Topological Sort (Kahn's Algorithm)

Order vertices such that for every edge u→v, u comes before v. Only works on DAGs.

public List<Integer> topologicalSort(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    int[] indegree = new int[n];
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        indegree[e[1]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : adj.get(node)) {
            if (--indegree[neighbor] == 0) queue.offer(neighbor);
        }
    }
    return order.size() == n ? order : List.of(); // empty if cycle
}

Deep Dive: Union-Find (Disjoint Set)

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // Path compression
        return parent[x];
    }
    boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
        return true;
    }
}

Common Interview Questions

• Number of Islands (BFS/DFS on grid)
• Clone Graph
• Course Schedule (topological sort)
• Word Ladder (BFS)
• Number of Connected Components (Union-Find)
• Shortest Path in Binary Matrix
• Pacific Atlantic Water Flow