🧠 Data Structures & Algorithms · Advanced

Graphs in Java

Adjacency lists, BFS, DFS, shortest paths (Dijkstra) at a conceptual level.

🧩 The mysteryMaps, social networks, airline routes, build dependencies: all graphs. Three algorithms answer most questions you'll ever ask them.

Vertices, edges, adjacency lists

A graph is a set of vertices connected by edges. The usual Java representation is an adjacency list: for each vertex, the list of its neighbors. It uses O(V + E) space, ideal for sparse graphs where most vertices connect to only a few others.

List<List<Integer>> adj = List.of(
    List.of(1, 2),  // 0 -> 1, 2
    List.of(3),     // 1 -> 3
    List.of(3),     // 2 -> 3
    List.of());     // 3

BFS: ripples in a pond

Breadth-first search explores level by level with a queue and a visited set. Everything 1 edge away, then 2 edges, and so on. Mark a vertex seen when you enqueue it, so it's never added twice. In an unweighted graph, BFS reaches each vertex along a path with the fewest edges.

🔮 Predict it

Trace a BFS

Graph g: 0 -> 2, 1; 1 -> 3; 2 -> 3, 4. What does this print?

var q = new ArrayDeque<>(List.of(0));
seen[0] = true;
while (!q.isEmpty()) {
    int v = q.poll();
    System.out.print(v + " ");
    for (int w : g.get(v))
        if (!seen[w]) {
            seen[w] = true; q.add(w);
        }
}

0 2 1 3 4
0 1 2 3 4
0 2 3 4 1
0 2 1 3 3 4

Show the answer

Round 1: print 0, enqueue 2 and 1 (in that order). Round 2: print 2, enqueue 3 and 4. Round 3: print 1; 3 is already seen, so it isn't added again. Then 3 and 4. Distance 0, then 1, then 2.

DFS: explore the maze

Depth-first search follows one path as deep as possible, then backtracks to the last fork, using recursion or an explicit stack. It's the tool for finding cycles, connected components and orderings, but its first path to a vertex can be long.

void dfs(int v) {
    if (seen[v]) return;
    seen[v] = true;
    System.out.print(v + " ");
    for (int w : g.get(v)) dfs(w);
}

🔮 Predict it

Same graph, depth first

Same graph, seen all false. What does dfs(0) print?

void dfs(int v) {
    if (seen[v]) return;
    seen[v] = true;
    System.out.print(v + " ");
    for (int w : g.get(v)) dfs(w);
}
// main: dfs(0);

0 2 3 4 1
0 2 1 3 4
0 1 3 2 4

Show the answer

DFS dives: 0, then its first neighbor 2, then 2's first neighbor 3 (a dead end). Back at 2, it visits 4. Back at 0, it finally visits 1, whose neighbor 3 is already seen.

Dijkstra: weighted shortest paths

With weighted edges, use Dijkstra: a priority queue always hands you the unvisited vertex with the smallest known distance, which is then final. That greedy choice is safe with non-negative weights: any other route to it passes through a farther vertex, so it can only be longer. Cost: O((V + E) log V).

⚠️ The trap

When the classics break

Dijkstra fails with negative edge weights: it finalizes a vertex as soon as it's closest, but a later negative edge could create a cheaper path. Use Bellman-Ford there. And for fewest hops in an unweighted graph, don't use DFS, which may find a long path first; use BFS.

💼 In the real world

Graphs at work

Navigation apps run Dijkstra-style searches, social apps use BFS for "friends of friends", and build tools order tasks by walking dependency graphs with DFS. Recognizing "this is a graph problem" is half the battle in interviews.

Key takeaways

Adjacency list: O(V + E) space, ideal for sparse graphs
BFS = queue + visited set; fewest-edges paths
DFS = recursion or stack; cycles, components, ordering
Dijkstra: PriorityQueue, non-negative weights only

💡 BFS is ripples spreading in a pond; DFS is exploring a maze by always taking the next unexplored corridor.

🤯 Did you know?

Edsger Dijkstra designed his shortest-path algorithm in 1956 in about twenty minutes, sitting at a cafe terrace in Amsterdam without pencil or paper.

Practice questions

Graph g: 0 → 1, 2; 1 → 3; 2 → 3, 4. seen[0] is true, the rest false. What does this BFS print?

var q = new ArrayDeque<>(List.of(0));
while (!q.isEmpty()) {
    int v = q.poll();
    System.out.print(v + " ");
    for (int w : g.get(v)) {
        if (!seen[w]) {
            seen[w] = true; q.add(w);
        }
    }
}

0 1 3 2 4
0 2 4 3 1
0 1 2 3 4
0 1 2 3 3 4

Check your answer

0 1 2 3 4. BFS finishes each distance level before the next: 0, then its neighbors 1 and 2, then 3 (found via 1) and 4 (via 2).

Graph g: 0 → 1, 2; 1 → 3; 2 → 3, 4. seen[] starts all false. What does dfs(0) print?

void dfs(int v) {
    if (seen[v]) return;
    seen[v] = true;
    System.out.print(v + " ");
    for (int w : g.get(v)) dfs(w);
}

0 1 3 2 4
0 1 2 3 4
0 2 4 3 1
0 1 3 4 2

Check your answer

0 1 3 2 4. DFS follows 0 -> 1 -> 3 as deep as possible, backtracks to 0, then visits 2; 3 is already seen, so it goes on to 4.

Next: generate every subset and permutation, and learn when to give up early.