Graphs

Graph problems test your ability to model relationships and traverse interconnected structures. They appear in every top-tier interview loop — Google, Meta, Amazon, and Apple all draw from this problem family. The good news: a small set of techniques covers the overwhelming majority of graph interview questions. This chapter gives you those techniques, with complete Java 25 implementations you can adapt to any problem.

Graph Representations

The Edge Record

Before building a graph class, define an edge. Java 25 records provide the ideal structure — immutable, compact, and readable:

public record Edge(int to, int weight) {}

For unweighted graphs, set weight to 1 or ignore it entirely. The record approach keeps edge data clean and eliminates boilerplate getters.

Adjacency List Implementation

The adjacency list is your go-to representation. It stores each vertex alongside its list of outgoing edges, consuming O(V + E) space — proportional to the graph’s actual size.

import java.util.*;

public class Graph {
    private final Map<Integer, List<Edge>> adjacencyList = new HashMap<>();
    private final boolean directed;

    public Graph(boolean directed) {
        this.directed = directed;
    }

    public void addVertex(int vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(int from, int to, int weight) {
        adjacencyList.computeIfAbsent(from, _ -> new ArrayList<>()).add(new Edge(to, weight));
        if (!directed) {
            adjacencyList.computeIfAbsent(to, _ -> new ArrayList<>()).add(new Edge(from, weight));
        }
    }

    public void addEdge(int from, int to) {
        addEdge(from, to, 1);
    }

    public List<Edge> neighbors(int vertex) {
        return adjacencyList.getOrDefault(vertex, List.of());
    }

    public Set<Integer> vertices() {
        return adjacencyList.keySet();
    }

    public int vertexCount() {
        return adjacencyList.size();
    }
}

The directed flag controls whether addEdge creates a one-way or two-way connection. This single class handles both directed and undirected graphs.

Adjacency Matrix Implementation

When the graph is dense or you need O(1) edge lookups, an adjacency matrix is the better choice:

public class GraphMatrix {
    private final int[][] matrix;
    private final boolean directed;
    private final int size;

    public GraphMatrix(int size, boolean directed) {
        this.size = size;
        this.directed = directed;
        this.matrix = new int[size][size];
        // Initialize with -1 to indicate no edge (0 could be a valid weight)
        for (int[] row : matrix) Arrays.fill(row, -1);
    }

    public void addEdge(int from, int to, int weight) {
        matrix[from][to] = weight;
        if (!directed) {
            matrix[to][from] = weight;
        }
    }

    public boolean hasEdge(int from, int to) {
        return matrix[from][to] != -1;
    }

    public int weight(int from, int to) {
        return matrix[from][to];
    }

    public List<Integer> neighbors(int vertex) {
        var result = new ArrayList<Integer>();
        for (int i = 0; i < size; i++) {
            if (matrix[vertex][i] != -1) result.add(i);
        }
        return result;
    }
}

For unweighted graphs, swap the int[][] for a boolean[][] matrix — each cell stores true or false. The adjacency matrix uses O(V²) space, so reserve it for graphs where V is small or E is close to V².

Topological Sort

A topological sort produces a linear ordering of vertices in a DAG such that for every directed edge (u, v), vertex u appears before vertex v. Build systems, course schedulers, and dependency resolvers all depend on topological ordering.

A topological sort exists if and only if the graph is a DAG. If the graph contains a cycle, no valid ordering exists.

Kahn’s Algorithm (BFS with In-Degree)

Kahn’s algorithm works by repeatedly removing vertices with zero in-degree — vertices that have no unsatisfied dependencies.

Algorithm:

Compute in-degree for every vertex.
Add all vertices with in-degree 0 to a queue.
While the queue is not empty: remove a vertex, add it to the result, and decrement the in-degree of all its neighbors. If any neighbor’s in-degree drops to 0, add it to the queue.
If the result contains all vertices, the ordering is valid. Otherwise, the graph has a cycle.

public List<Integer> topologicalSortKahn(Graph graph) {
    Map<Integer, Integer> inDegree = new HashMap<>();
    for (int v : graph.vertices()) {
        inDegree.putIfAbsent(v, 0);
        for (Edge edge : graph.neighbors(v)) {
            inDegree.merge(edge.to(), 1, Integer::sum);
        }
    }

    Queue<Integer> queue = new LinkedList<>();
    for (var entry : inDegree.entrySet()) {
        if (entry.getValue() == 0) queue.add(entry.getKey());
    }

    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int current = queue.poll();
        order.add(current);
        for (Edge edge : graph.neighbors(current)) {
            int newDegree = inDegree.merge(edge.to(), -1, Integer::sum);
            if (newDegree == 0) queue.add(edge.to());
        }
    }

    if (order.size() != graph.vertexCount()) {
        throw new IllegalArgumentException("Graph contains a cycle — no topological order exists");
    }
    return order;
}

Time: O(V + E) — each vertex and edge is processed once. Space: O(V) for the in-degree map and queue.

DFS-Based Topological Sort

The DFS approach uses a different insight: when DFS finishes processing a vertex (all descendants have been visited), that vertex can appear after all its dependents. Collecting vertices in post-order and reversing the result produces a valid topological ordering.

public List<Integer> topologicalSortDFS(Graph graph) {
    Set<Integer> visited = new HashSet<>();
    Deque<Integer> stack = new ArrayDeque<>();

    for (int vertex : graph.vertices()) {
        if (!visited.contains(vertex)) {
            dfsTopSort(graph, vertex, visited, stack);
        }
    }

    return new ArrayList<>(stack);
}

private void dfsTopSort(Graph graph, int vertex, Set<Integer> visited, Deque<Integer> stack) {
    visited.add(vertex);
    for (Edge edge : graph.neighbors(vertex)) {
        if (!visited.contains(edge.to())) {
            dfsTopSort(graph, edge.to(), visited, stack);
        }
    }
    stack.push(vertex);  // Post-order: add after all descendants are processed
}

Time: O(V + E). Space: O(V) for the visited set and recursion stack.

Which to use in interviews? Kahn’s algorithm is easier to reason about and naturally detects cycles (the result size check). The DFS approach is more concise. Know both — interviewers sometimes ask for the alternative after you present one.

Applications

Course Schedule: Given course prerequisites, find a valid enrollment order — or determine that no valid order exists (cycle).
Build Order: Compile source files in dependency order so every file is compiled after its dependencies.
Dependency Resolution: Package managers (Maven, npm) use topological sort to determine installation order.

Cycle Detection

Directed Graphs: Three-Color DFS

The three-color approach assigns each vertex a state during DFS. If DFS encounters a vertex that is currently being processed (GRAY), a cycle exists — the traversal has looped back to an ancestor in the current path.

public enum Color { WHITE, GRAY, BLACK }

public boolean hasCycleDirected(Graph graph) {
    Map<Integer, Color> color = new HashMap<>();
    for (int v : graph.vertices()) {
        color.put(v, Color.WHITE);
    }

    for (int v : graph.vertices()) {
        if (color.get(v) == Color.WHITE) {
            if (dfsCycleDirected(graph, v, color)) return true;
        }
    }
    return false;
}

private boolean dfsCycleDirected(Graph graph, int vertex, Map<Integer, Color> color) {
    color.put(vertex, Color.GRAY);  // Mark as in-progress

    for (Edge edge : graph.neighbors(vertex)) {
        Color neighborColor = color.get(edge.to());
        if (neighborColor == Color.GRAY) return true;   // Back edge → cycle
        if (neighborColor == Color.WHITE) {
            if (dfsCycleDirected(graph, edge.to(), color)) return true;
        }
    }

    color.put(vertex, Color.BLACK);  // Mark as fully processed
    return false;
}

WHITE = unvisited. GRAY = currently on the recursion stack (being explored). BLACK = fully processed (all descendants explored). A GRAY→GRAY edge proves a cycle because the destination is an ancestor in the current DFS path.