Graphs in Java: BFS, DFS, and Topological Sort

Grid problems, dependency ordering, and social-network questions are all graph problems wearing different clothes. The representation is the first decision.

Building the graph

import java.util.*;

public class Representation {
    public static void main(String[] args) {
        int[][] edges = {{0,1},{0,2},{1,2},{2,3}};

        Map<Integer, List<Integer>> adjMap = new HashMap<>();
        for (int[] e : edges) {
            adjMap.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
            adjMap.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]);   // undirected
        }

        int n = 4;
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) adjList.add(new ArrayList<>());
        for (int[] e : edges) { adjList.get(e[0]).add(e[1]); adjList.get(e[1]).add(e[0]); }

        boolean[][] matrix = new boolean[n][n];
        for (int[] e : edges) { matrix[e[0]][e[1]] = true; matrix[e[1]][e[0]] = true; }

        System.out.println("map form:   " + new TreeMap<>(adjMap));
        System.out.println("list form:  " + adjList);
        System.out.println("matrix row 2: " + Arrays.toString(matrix[2]));
        System.out.printf("list memory O(V+E)=%d entries, matrix O(V^2)=%d cells%n",
                          adjList.stream().mapToInt(List::size).sum(), n * n);
    }
}

$ java Representation.java
map form:   {0=[1, 2], 1=[0, 2], 2=[0, 1, 3], 3=[2]}
list form:  [[1, 2], [0, 2], [1, 0, 3], [2]]
matrix row 2: [true, true, false, true]
list memory O(V+E)=8 entries, matrix O(V^2)=16 cells

Row 2 reads “node 2 connects to 0, 1, and 3, but not to itself”. Choosing between the three:

• List<List<Integer>> when nodes are 0..n-1, which competitive-style problems guarantee. Fastest and no boxing on the outer index.
• Map<T, List<T>> when nodes are strings, coordinates, or arbitrary objects.
• Adjacency matrix only for dense graphs or when you need O(1) edge lookup. At 10,000 nodes it is 100 million cells.

BFS finds shortest paths; DFS does not

import java.util.*;

public class ShortestPath {
    static Map<String, Integer> bfsDistances(Map<String, List<String>> g, String start) {
        Map<String, Integer> dist = new LinkedHashMap<>();
        dist.put(start, 0);
        Deque<String> queue = new ArrayDeque<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            String node = queue.poll();
            for (String nb : g.getOrDefault(node, List.of())) {
                if (!dist.containsKey(nb)) {          // mark on ENQUEUE
                    dist.put(nb, dist.get(node) + 1);
                    queue.offer(nb);
                }
            }
        }
        return dist;
    }

    static List<String> shortestPath(Map<String, List<String>> g, String start, String goal) {
        if (start.equals(goal)) return List.of(start);
        Map<String, String> parent = new HashMap<>();
        parent.put(start, null);
        Deque<String> queue = new ArrayDeque<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            String node = queue.poll();
            for (String nb : g.getOrDefault(node, List.of())) {
                if (parent.containsKey(nb)) continue;
                parent.put(nb, node);
                if (nb.equals(goal)) {
                    LinkedList<String> path = new LinkedList<>();
                    for (String c = goal; c != null; c = parent.get(c)) path.addFirst(c);
                    return path;
                }
                queue.offer(nb);
            }
        }
        return List.of();
    }

    public static void main(String[] args) {
        Map<String, List<String>> g = Map.of(
            "A", List.of("B", "C"),
            "B", List.of("A", "D"),
            "C", List.of("A", "D"),
            "D", List.of("B", "C", "E"),
            "E", List.of("D"));

        System.out.println("distances from A: " + new TreeMap<>(bfsDistances(g, "A")));
        System.out.println("A -> E:           " + shortestPath(g, "A", "E"));
        System.out.println("A -> Z:           " + shortestPath(g, "A", "Z"));
    }
}

$ java ShortestPath.java
distances from A: {A=0, B=1, C=1, D=2, E=3}
A -> E:           [A, B, D, E]
A -> Z:           []

BFS visits in hop order, so the first arrival at a node is via a shortest path. DFS would also find a path to E, but not necessarily the shortest — it commits to one branch to the end.

Mark on enqueue, not on dequeue. With Map<String,String> parent doubling as the visited set here, parent.containsKey(nb) is checked and set at the moment of enqueuing. Deferring the mark lets the same node enter the queue once per incoming edge.

Reconstructing the path from parent is O(path length). LinkedList.addFirst is O(1); building with ArrayList.add(0, x) would be O(n) per insert.

DFS: recursive and iterative

import java.util.*;

public class Dfs {
    static void recursive(Map<Integer, List<Integer>> g, int node,
                          Set<Integer> visited, List<Integer> order) {
        if (!visited.add(node)) return;
        order.add(node);
        for (int nb : g.getOrDefault(node, List.of())) recursive(g, nb, visited, order);
    }

    static List<Integer> iterative(Map<Integer, List<Integer>> g, int start) {
        List<Integer> order = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited.add(node)) continue;
            order.add(node);
            List<Integer> nbs = g.getOrDefault(node, List.of());
            for (int i = nbs.size() - 1; i >= 0; i--) stack.push(nbs.get(i));  // reverse for order
        }
        return order;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> g = Map.of(
            1, List.of(2, 3), 2, List.of(4), 3, List.of(4), 4, List.of(5), 5, List.of());

        List<Integer> a = new ArrayList<>();
        recursive(g, 1, new HashSet<>(), a);
        System.out.println("recursive: " + a);
        System.out.println("iterative: " + iterative(g, 1));

        Map<Integer, List<Integer>> chain = new HashMap<>();
        for (int i = 0; i < 100_000; i++) chain.put(i, List.of(i + 1));
        chain.put(100_000, List.of());
        System.out.println("iterative on 100k chain: " + iterative(chain, 0).size());
        try {
            List<Integer> out = new ArrayList<>();
            recursive(chain, 0, new HashSet<>(), out);
            System.out.println("recursive on 100k chain: " + out.size());
        } catch (StackOverflowError e) {
            System.out.println("recursive on 100k chain: StackOverflowError");
        }
    }
}

$ java Dfs.java
recursive: [1, 2, 4, 5, 3]
iterative: [1, 2, 4, 5, 3]
iterative on 100k chain: 100001
recursive on 100k chain: StackOverflowError

The reverse push in the iterative version makes the two agree. Without it, a stack pops the last neighbour first and the orders diverge — usually acceptable, occasionally the thing being tested.

visited.add(node) returning false when already present replaces a separate contains check.

Cycle detection needs three colours

import java.util.*;

public class CycleDetect {
    enum Colour { WHITE, GREY, BLACK }

    static boolean naive(Map<Integer, List<Integer>> g, int node, Set<Integer> visited) {
        if (!visited.add(node)) return true;            // WRONG: "seen" is not "on the path"
        for (int nb : g.getOrDefault(node, List.of()))
            if (naive(g, nb, visited)) return true;
        return false;
    }

    static boolean hasCycle(Map<Integer, List<Integer>> g) {
        Map<Integer, Colour> colour = new HashMap<>();
        for (int node : g.keySet())
            if (colour.getOrDefault(node, Colour.WHITE) == Colour.WHITE && visit(g, node, colour))
                return true;
        return false;
    }

    static boolean visit(Map<Integer, List<Integer>> g, int node, Map<Integer, Colour> colour) {
        colour.put(node, Colour.GREY);                  // on the current path
        for (int nb : g.getOrDefault(node, List.of())) {
            Colour c = colour.getOrDefault(nb, Colour.WHITE);
            if (c == Colour.GREY) return true;          // back edge — a real cycle
            if (c == Colour.WHITE && visit(g, nb, colour)) return true;
        }
        colour.put(node, Colour.BLACK);                 // fully explored
        return false;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> diamond = Map.of(
            1, List.of(2, 3), 2, List.of(4), 3, List.of(4), 4, List.of());
        Map<Integer, List<Integer>> cyclic = Map.of(
            1, List.of(2), 2, List.of(3), 3, List.of(1));

        System.out.println("diamond DAG, naive:  " + naive(diamond, 1, new HashSet<>()));
        System.out.println("diamond DAG, colour: " + hasCycle(diamond));
        System.out.println("real cycle, colour:  " + hasCycle(cyclic));
    }
}

$ java CycleDetect.java
diamond DAG, naive:  true
diamond DAG, colour: false
real cycle, colour:  true

The naive version reports a cycle in the diamond because node 4 is reachable by two different paths. “Already seen” is not “currently on the path” — that distinction is the entire reason for the third colour. Grey means “an ancestor in the current DFS”; reaching a grey node is a back edge and a genuine cycle. Black means “finished, and everything below it is fine”.

One Java caution in that outer loop: g.keySet() on a HashMap or Map.of has unspecified iteration order. A cycle is found from any starting node so the answer is stable here, but for anything where the reported cycle or ordering matters, wrap it — for (int node : new TreeSet<>(g.keySet())) — or index nodes 0..n-1 with a List<List<Integer>>.

Grids are graphs

import java.util.*;

public class Islands {
    static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};

    static int countIslands(char[][] grid) {
        if (grid.length == 0) return 0;
        int rows = grid.length, cols = grid[0].length, count = 0;
        boolean[][] seen = new boolean[rows][cols];
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == '1' && !seen[r][c]) { count++; flood(grid, seen, r, c); }
        return count;
    }

    static void flood(char[][] grid, boolean[][] seen, int sr, int sc) {
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[]{sr, sc});
        seen[sr][sc] = true;
        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            for (int[] d : DIRS) {
                int r = cell[0] + d[0], c = cell[1] + d[1];
                if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) continue;
                if (seen[r][c] || grid[r][c] != '1') continue;
                seen[r][c] = true;                    // mark on push
                stack.push(new int[]{r, c});
            }
        }
    }

    public static void main(String[] args) {
        char[][] grid = {
            "11000".toCharArray(),
            "11000".toCharArray(),
            "00100".toCharArray(),
            "00011".toCharArray()};
        System.out.println("islands: " + countIslands(grid));
        System.out.println("empty:   " + countIslands(new char[0][0]));
    }
}

$ java Islands.java
islands: 3
empty:   0

A grid cell is a node and its four neighbours are its edges — no explicit graph needed. The DIRS array is the idiom; writing four separate recursive calls is the version that gets a bounds check wrong.

Iterative flood fill rather than recursive because a 1000×1000 all-land grid is a million-deep recursion.

Topological sort: Kahn’s algorithm

import java.util.*;

public class TopoSort {
    static List<Integer> topoSort(int n, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] indegree = new int[n];
        for (int[] p : prerequisites) { adj.get(p[1]).add(p[0]); indegree[p[0]]++; }

        Deque<Integer> ready = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indegree[i] == 0) ready.offer(i);

        List<Integer> order = new ArrayList<>();
        while (!ready.isEmpty()) {
            int node = ready.poll();
            order.add(node);
            for (int nb : adj.get(node)) if (--indegree[nb] == 0) ready.offer(nb);
        }
        return order.size() == n ? order : List.of();     // short == a cycle
    }

    public static void main(String[] args) {
        System.out.println("4 courses, chain:  " + topoSort(4, new int[][]{{1,0},{2,1},{3,2}}));
        System.out.println("diamond:           " + topoSort(4, new int[][]{{1,0},{2,0},{3,1},{3,2}}));
        System.out.println("cyclic:            " + topoSort(2, new int[][]{{1,0},{0,1}}));
        System.out.println("no edges:          " + topoSort(3, new int[][]{}));
    }
}

$ java TopoSort.java
4 courses, chain:  [0, 1, 2, 3]
diamond:           [0, 1, 2, 3]
cyclic:            []
no edges:          [0, 1, 2]

The algorithm in three sentences: count incoming edges; queue everything with zero; each time you remove a node, decrement its successors and queue any that hit zero.

The length check is the cycle detection. If order.size() < n, the missing nodes are all waiting on each other and none ever reached in-degree zero — which is precisely the “is this course schedule possible?” question.

Note {p[0], p[1]} ordering: the input {a, b} means “b before a”, so the edge runs b -> a. Getting that backwards produces a valid-looking order that is exactly reversed — read the problem statement twice.

Recognising it

SIGNAL                                          APPROACH
"shortest path", "fewest steps", unweighted     BFS
"minimum moves on a grid or board"              BFS
"is there a path", "connected components"       DFS or BFS, either works
"detect a cycle" (directed)                     three-colour DFS
"detect a cycle" (undirected)                   DFS tracking the parent, or union-find
"order tasks with dependencies"                 topological sort, Kahn's
"is this schedule possible"                     topological sort + length check
grid / maze / islands / rotting oranges         grid BFS or DFS with a DIRS array
weighted edges, shortest path                   Dijkstra with a PriorityQueue — not plain BFS

That last line is the frequent mistake: BFS is only shortest-path on unweighted graphs.

Practice

diamond DAG, naive: true      (wrong)

The traversal still terminates, but a node is enqueued once per incoming edge.

cyclic: []

Order is unspecified — the result can differ between runs and JDK versions.

Next: sorting, binary search, and heaps — comparators without overflow, and the PriorityQueue top-k pattern.