گراف‌ها و الگوریتم‌های گرافGraphs & Graph Algorithms

Let's start with the secret that separates seniors from juniors: most hard interview problems are secretly graph problems wearing a disguise. A city map, a grid of cells, a list of course prerequisites, an app's friend network, even "can I get from state A to state B under these rules" — they are all graphs. Once you learn to see the graph hidden inside a problem, you are halfway to the solution. This chapter teaches you that seeing from the ground up, then unpacks the algorithmic toolbox one piece at a time.

Part 0 — words you must know

Before anything, let's attach a mental picture to each word so none of them feel foreign later.

With that picture the formal definition becomes easy: a graph is G = (V, E) — a set of vertices V and a set of edges E ⊆ V × V (each edge is a pair of vertices). Two symbols you'll see all chapter:

• V = |V| means the number of vertices.
• E = |E| means the number of edges.

Every time and space complexity below is written in terms of these two numbers.

Two more adjectives we'll need:

Finally, DAG: short for Directed Acyclic Graph, a directed graph with no cycles. "Acyclic" means you can't start at a vertex, follow the edges' direction, and end up back at it. This family is important enough to have several algorithms of its own.

Mental model: four questions before any algorithm

The real skill is modeling: reading a word problem and spotting the vertices, edges, and weights, then reaching for the right traversal. A 2D grid is a graph (each cell a vertex, each adjacency an edge), a dependency chain is a graph, a state machine is a graph.

If you write those four facts (direction, weights, density, cyclicity) on paper before coding, in half your interviews the algorithm falls right out.

Representations: how to store a graph in memory

Before any algorithm, we must store the graph. There are three common ways, each built for a different job.

Adjacency list

Each vertex stores its list of neighbors. Space is O(V + E) (as much as vertices plus edges, no more). Iterating a vertex's neighbors is O(deg(v)) — as many as that city's roads. Checking whether a specific edge (u, v) exists is O(deg(u)) unless you store neighbors in a set.

// V vertices labeled 0..V-1. Weighted directed edges.
class Graph {
    record Edge(int to, int weight) {}
    final List<List<Edge>> adj;

    Graph(int v) {
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
    }

    void addDirected(int u, int v, int w) { adj.get(u).add(new Edge(v, w)); }
    void addUndirected(int u, int v, int w) {
        adj.get(u).add(new Edge(v, w));
        adj.get(v).add(new Edge(u, w)); // both directions
    }
}

Notice addUndirected adds the edge in both directions — a two-way road is seen from both cities. For a purely unweighted graph, int[][] adj where adj[u] is a plain neighbor array is leaner and more cache-friendly (data sits contiguously, so the CPU reads it faster).

Adjacency matrix

This is boolean[V][V] (or int[V][V] for weights). Space is O(V²). An edge-existence check is O(1) (constant time) — one cell lookup. But iterating neighbors is O(V) regardless of degree (you must scan a whole row), and the memory is prohibitive for large sparse graphs. Reach for it only when V is small (say ≤ ~1000), the graph is dense, or you truly need constant-time edge queries (e.g. Floyd–Warshall).

int[][] w = new int[V][V];
for (int[] row : w) Arrays.fill(row, INF);
for (int i = 0; i < V; i++) w[i][i] = 0;
// w[u][v] = weight of edge u->v, INF if none

Edge list

Just a List<int[]> of triples {u, v, w} — "from u to v with weight w." Compact and simple, and exactly what Kruskal's MST and Bellman-Ford consume. Its downside: to ask "who are u's neighbors?" you'd scan the whole list, so it's bad for traversal.

BFS — breadth-first search

To keep these rings in order, BFS uses a FIFO queue (First-In-First-Out; whoever entered first leaves first — like a bakery line). On an unweighted graph it computes shortest paths (fewest edges) in O(V + E). This is the single most reused graph technique in interviews: every "fewest steps / moves / transformations" problem is secretly BFS.

int[] bfsDistances(List<List<Integer>> adj, int src) {
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, -1);          // -1 = unvisited
    Deque<Integer> q = new ArrayDeque<>();
    dist[src] = 0;
    q.add(src);
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {    // mark on ENQUEUE, not on dequeue
                dist[v] = dist[u] + 1;
                q.add(v);
            }
        }
    }
    return dist;
}

Two important BFS variants that come up constantly:

• Multi-source BFS: seed the queue with all sources at distance 0 (think "rotting oranges" or "nearest exit"). In one pass it computes, for every cell, the distance to the nearest source — like dropping several stones in the pond at once.
• 0-1 BFS: when edge weights are only 0 or 1, use a deque (double-ended queue) instead of a plain queue: push 0-weight edges to the front, 1-weight edges to the back. Gives Dijkstra-quality results at O(V + E) cost.

DFS — depth-first search

The recursive version is the most natural way to write it. An iterative version with an explicit stack avoids stack overflow on very deep graphs (the JVM's default stack handles roughly 10k–20k call frames — a graph with one long path of 100k nodes will throw StackOverflowError).

void dfs(int u, List<List<Integer>> adj, boolean[] visited) {
    visited[u] = true;
    // preorder work here
    for (int v : adj.get(u)) {
        if (!visited[v]) dfs(v, adj, visited);
    }
    // postorder work here (finish time)
}

Two words matter here: preorder work is what you do before descending into children, and postorder work is what you do after all children finish. The moment all of a vertex's descendants are done is that vertex's finish time.

DFS is the backbone of: connected components, cycle detection, topological sort, bridges/articulation points (Tarjan's algorithm), and strongly-connected components (SCC, via Tarjan or Kosaraju). The key idea powering topo sort and SCC is that postorder finish time.

Connected components (undirected)

A connected component is an isolated piece of the graph whose vertices are all reachable from each other but not from the rest — like several separate islands with internal roads but no bridges between them. We want to count or label these islands.

The method is simple: launch a BFS (or DFS) from every not-yet-visited vertex; every time you're forced to start fresh, you've found a new island.

int countComponents(int n, List<List<Integer>> adj) {
    boolean[] seen = new boolean[n];
    int components = 0;
    for (int i = 0; i < n; i++) {
        if (!seen[i]) {
            components++;
            Deque<Integer> q = new ArrayDeque<>();
            seen[i] = true; q.add(i);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u))
                    if (!seen[v]) { seen[v] = true; q.add(v); }
            }
        }
    }
    return components;
}

Total cost is O(V + E). But note: this works when you have the whole graph at once. For dynamic connectivity — edges arriving one at a time while you keep asking "are these two connected now?" — the right tool is something else called Union-Find, which we'll meet shortly.

Cycle detection

A "cycle" is a path that starts at a vertex and returns to it. Cycle detection is completely different for directed vs undirected graphs, and that's where the common mistakes live.

Undirected case

An undirected cycle exists if, during DFS, you reach an already-visited neighbor that is not the parent you just came from.

boolean hasCycleUndirected(int n, List<List<Integer>> adj) {
    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (!visited[i] && dfsUndir(i, -1, adj, visited)) return true;
    }
    return false;
}
boolean dfsUndir(int u, int parent, List<List<Integer>> adj, boolean[] visited) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            if (dfsUndir(v, u, adj, visited)) return true;
        } else if (v != parent) {   // visited and not where we came from => cycle
            return true;
        }
    }
    return false;
}

One subtle trap: with parallel edges — two separate edges between the same pair of vertices — the v != parent test is insufficient, because two edges to the parent really are a genuine 2-cycle. There you'd use Union-Find or track edge identity.

Directed case

Here, reaching a "visited" neighbor is not enough. The vertex must be on the current recursion stack — one of your ancestors on the present path, not a vertex whose work already finished. To distinguish, we use three colors.

boolean hasCycleDirected(int n, List<List<Integer>> adj) {
    int[] color = new int[n];       // 0=white, 1=gray, 2=black
    for (int i = 0; i < n; i++)
        if (color[i] == 0 && dfsDir(i, adj, color)) return true;
    return false;
}
boolean dfsDir(int u, List<List<Integer>> adj, int[] color) {
    color[u] = 1;                   // gray: on stack
    for (int v : adj.get(u)) {
        if (color[v] == 1) return true;               // back edge -> cycle
        if (color[v] == 0 && dfsDir(v, adj, color)) return true;
    }
    color[u] = 2;                   // black: fully explored
    return false;
}

Only reaching a gray node is a cycle; reaching a black node is a finished subtree (a cross or forward edge), which is perfectly fine. Confusing "visited" with "on the stack" is a top-three senior interview mistake — take it seriously.

Topological sort (on DAGs)

Formally: a linear ordering of a DAG's vertices such that every edge u → v places u before v. This ordering exists if and only if the graph has no cycle. Uses: build systems, task scheduling, course prerequisites, package dependency resolution, and DP on a DAG. There are two common methods.

Kahn's algorithm (BFS / in-degree)

A vertex's in-degree is the number of edges pointing into it — how many prerequisites it has. Idea: repeatedly emit any vertex whose in-degree has dropped to 0 (no remaining prerequisites), and decrement its neighbors' in-degrees. Repeat.

int[] topoKahn(int n, List<List<Integer>> adj) {
    int[] indeg = new int[n];
    for (int u = 0; u < n; u++)
        for (int v : adj.get(u)) indeg[v]++;
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
    int[] order = new int[n];
    int idx = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx++] = u;
        for (int v : adj.get(u))
            if (--indeg[v] == 0) q.add(v);
    }
    if (idx != n) throw new IllegalStateException("graph has a cycle");
    return order;
}

A subtle follow-up an interviewer might ask: if you use a PriorityQueue instead of a plain queue, you get the lexicographically smallest topological order.

DFS-based topological sort

The second method: push each vertex onto a stack in postorder (after all its descendants finish), then reverse the stack. Intuition: a vertex only "finishes" after everything reachable from it has finished; so the reverse of finish order respects every edge.

List<Integer> topoDfs(int n, List<List<Integer>> adj) {
    int[] color = new int[n];       // reuse the 3-color scheme to also detect cycles
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++)
        if (color[i] == 0) topoVisit(i, adj, color, stack);
    List<Integer> order = new ArrayList<>(n);
    while (!stack.isEmpty()) order.add(stack.pop()); // reverse of finish order
    return order;
}
void topoVisit(int u, List<List<Integer>> adj, int[] color, Deque<Integer> stack) {
    color[u] = 1;
    for (int v : adj.get(u)) {
        if (color[v] == 1) throw new IllegalStateException("cycle");
        if (color[v] == 0) topoVisit(v, adj, color, stack);
    }
    color[u] = 2;
    stack.push(u);                  // postorder push
}

Both methods are O(V + E). Kahn is easier to reason about and detects cycles cleanly; DFS is more elegant and reuses the three-color machinery from the previous section.

Shortest paths

Here's a hard rule: match the algorithm to the edge weights. Picking the wrong one is a red flag to interviewers. Memorize this table; it is essentially the whole decision:

Dijkstra

Crucial: Dijkstra is correct only with non-negative weights. Why? Its greedy assumption is that once it finalizes a vertex, no cheaper path exists. A negative-weight edge can break that assumption and make an already-"finalized" vertex cheaper.

int[] dijkstra(List<List<int[]>> adj, int src) { // adj: int[]{to, weight}
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    // {distance, vertex}, ordered by distance
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.add(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int d = top[0], u = top[1];
        if (d > dist[u]) continue;          // STALE entry — skip. Critical.
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.add(new int[]{dist[v], v}); // lazy deletion: push a fresh entry
            }
        }
    }
    return dist;
}

Two things separate a correct answer from a buggy one:

To recover the actual path (not just its length), keep an int[] prev array and set prev[v] = u on each successful relaxation; then walk backward from the target to the source.

Bellman–Ford

When weights can be negative, or when you must detect a negative cycle, Dijkstra is useless and you reach for Bellman-Ford.

long[] bellmanFord(int n, List<int[]> edges, int src) { // edges: {u, v, w}
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != Long.MAX_VALUE && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    for (int[] e : edges) {         // one more pass -> negative cycle if it relaxes
        int u = e[0], v = e[1], w = e[2];
        if (dist[u] != Long.MAX_VALUE && dist[u] + w < dist[v])
            throw new IllegalStateException("negative cycle reachable from src");
    }
    return dist;
}

This is the algorithm behind real-world problems like arbitrage detection (profit from a loop of currency conversions) — because arbitrage is exactly a negative cycle in the graph of exchange rates.

Shortest path on a DAG

If the graph is a DAG (no cycle), then even with negative weights you have a simpler, faster solution: process vertices in topological order and relax each one's outgoing edges. Because a vertex is finalized before any of its successors, a single pass suffices — negative weights are fine — and it runs in O(V + E). The very same frame is the skeleton for longest-path / critical-path (CPM) problems: just negate the weights or relax with max instead of min.

Union-Find (Disjoint Set Union)

This structure answers dynamic connectivity ("are x and y in the same set now?"), powers Kruskal's MST, and detects cycles as you add undirected edges. Two optimizations make it lightning fast:

• Union by rank/size: when merging, attach the smaller tree under the larger to keep trees shallow (the small club moves under the big club's banner, not the reverse).
• Path compression: during find, repoint every node you pass directly to the root, so next time the question is shorter.

class DSU {
    private final int[] parent, rank;
    private int count;              // number of disjoint sets

    DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) parent[i] = i; // each node its own root
    }

    int find(int x) {               // path compression (iterative, no stack overflow)
        int root = x;
        while (root != parent[root]) root = parent[root];
        while (x != root) { int next = parent[x]; parent[x] = root; x = next; }
        return root;
    }

    boolean union(int a, int b) {   // returns false if already in same set
        int ra = find(a), rb = find(b);
        if (ra == rb) return false; // a cycle would be created if this were an edge
        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;            // attach smaller rank under larger
        if (rank[ra] == rank[rb]) rank[ra]++;
        count--;
        return true;
    }

    boolean connected(int a, int b) { return find(a) == find(b); }
    int components() { return count; }
}

Notice find is written iteratively on purpose, not recursively — to avoid StackOverflowError on very long chains.

Cycle detection with DSU (undirected): iterate the edges; if union(u, v) returns false, the two endpoints were already in the same set, so this edge closes a cycle. This is the cleanest way to detect a cycle while you're still building the graph, and it naturally handles parallel edges too.

boolean hasCycle(int n, List<int[]> edges) {
    DSU dsu = new DSU(n);
    for (int[] e : edges)
        if (!dsu.union(e[0], e[1])) return true; // edge inside an existing tree
    return false;
}

Minimum spanning tree (MST)

Formally: given a connected, weighted, undirected graph, an MST is a subset of edges connecting all vertices with minimum total weight — exactly V − 1 edges and no cycle. Both algorithms below rest on a single principle:

Kruskal — sort edges, add greedily, DSU to reject cycles

int kruskalMST(int n, List<int[]> edges) { // edges: {u, v, w}
    edges.sort(Comparator.comparingInt(e -> e[2])); // lightest first
    DSU dsu = new DSU(n);
    int total = 0, used = 0;
    for (int[] e : edges) {
        if (dsu.union(e[0], e[1])) {    // adding it doesn't create a cycle
            total += e[2];
            if (++used == n - 1) break; // MST complete
        }
    }
    if (used != n - 1) throw new IllegalStateException("graph is not connected");
    return total;
}

The logic is intuitive: sort edges from light to heavy, try each in turn; if its endpoints weren't already connected (union returned true) take it, otherwise skip it since it would only form a cycle. Cost is O(E log E), dominated by the sort. Best when the graph is sparse or edges are already sorted. Kruskal is the canonical use case for Union-Find.

Prim — grow one tree, always take the cheapest edge leaving it

int primMST(List<List<int[]>> adj, int n) {   // adj: {to, weight}
    boolean[] inTree = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.add(new int[]{0, 0});               // {weight, vertex}, start at 0
    int total = 0, picked = 0;
    while (!pq.isEmpty() && picked < n) {
        int[] top = pq.poll();
        int w = top[0], u = top[1];
        if (inTree[u]) continue;           // already absorbed — skip stale entry
        inTree[u] = true;
        total += w;
        picked++;
        for (int[] e : adj.get(u))
            if (!inTree[e[0]]) pq.add(new int[]{e[1], e[0]});
    }
    if (picked != n) throw new IllegalStateException("graph is not connected");
    return total;
}

Instead of sorting all edges, Prim starts a tree from one vertex and, at each step, grabs the cheapest edge leaving the current tree. Cost is O(E log V) with a binary heap. Prim shines on dense graphs (especially with a Fibonacci heap or an adjacency-matrix O(V²) variant).

Choosing between them: sparse input or an edge list → Kruskal; a dense graph or when you already have adjacency lists → Prim. Both give a minimum total weight (the total is unique if all weights are distinct; the tree itself may not be unique).

Common pitfalls

Skim this list once before any interview — each is a real mistake that has burned seniors.

• BFS marking on dequeue instead of enqueue → nodes enqueued repeatedly, distances wrong.
• Dijkstra with negative edges → silently wrong answers. Reach for Bellman-Ford.
• Forgetting the stale-entry guard in heap-based Dijkstra/Prim → slower, and if mishandled, wrong.
• Integer overflow on dist + w near Integer.MAX_VALUE → negative distances. Use long or a guard.
• Directed cycle detection with plain visited → false positives from cross edges. You need on-stack (gray) state.
• Undirected cycle detection ignoring the parent → every tree edge looks like a cycle. Skip the immediate parent (but beware parallel edges).
• Deep recursion on long-path graphs → StackOverflowError. Convert to iterative or raise -Xss.
• Disconnected graphs → a single BFS/DFS launch misses components; loop over all start vertices. MST on a disconnected graph doesn't exist (you get a forest).
• Using an adjacency matrix for a large sparse graph → O(V²) memory blowup.

Best practices

• On hot paths, default to adjacency lists with primitive-friendly structures.
• Encapsulate DSU once and reuse it everywhere — it appears constantly (MST, connectivity, "accounts merge", "number of islands II", "redundant connection").
• Where recursion depth is unbounded by input size, prefer iterative BFS/DSU.
• State the complexity and why the algorithm is correct for the given weight profile; interviewers grade the justification, not just the code.
• When modeling, write down V, E, direction, and weight range first — the algorithm falls out of those four facts.

Interview Questions

Deque<Integer> q = new ArrayDeque<>();
q.add(src);
while (!q.isEmpty()) {
    int u = q.poll();
    visited[u] = true;                 // <-- here
    for (int v : adj.get(u))
        if (!visited[v]) q.add(v);
}

// Directed edges: 0->1, 1->2, 2->0, 3->2. topoKahn(4, adj) called.