Skip to content
Tutorials Center
My learning

Topics

Lesson 193 of 201 ยท Data Structures and Algorithms

Graphs, Recursion and Backtracking

Build graphs in Java with adjacency lists, explore them with BFS and DFS, find shortest paths and run Dijkstra with PriorityQueue, then solve puzzles with backtracking.

A graph is a set of things and the connections between them. Cities and roads, people and friendships, web pages and links, tasks and the tasks they depend on, rooms in a game and the doors between them: once you see the pattern, graphs are everywhere. Route planners, package managers, social networks and compilers all run graph algorithms constantly.

This lesson builds a graph from plain Java collections and teaches the algorithms that matter most: breadth-first search (BFS) and depth-first search (DFS) for exploring, BFS again for the shortest path when every step costs the same, and Dijkstra's algorithm with a PriorityQueue when steps have different costs. The second half turns to backtracking, a style of recursion that searches through choices, and solves permutations, subsets and the N-Queens puzzle.

You'll want to be comfortable with HashMap, Queues, Deques and PriorityQueue and records. The queue and stack ideas come from Data Structures in Java.

Graph vocabulary

A graph has vertices (also called nodes) and edges that connect pairs of vertices.

  • In an undirected graph, an edge goes both ways: if Ana is friends with Ben, Ben is friends with Ana.
  • In a directed graph, edges have a direction: page A links to page B, but B may not link back. Task "deploy" depends on task "test", not the other way around.
  • In a weighted graph, every edge has a number, such as a distance in kilometers or a travel time in minutes.
  • Two vertices are neighbors (adjacent) if an edge connects them. A vertex's degree is its number of edges.
  • A path is a sequence of vertices connected by edges; a cycle is a path that returns to its start. A directed graph with no cycles is a DAG, the shape of every build system's dependency graph.

Storing a graph: adjacency list or matrix

There are two standard representations:

Adjacency list Adjacency matrix
Idea each vertex keeps a list of its neighbors an n ร— n boolean[][] (or weights)
Memory O(V + E) O(Vยฒ)
"Is there an edge uโ€“v?" O(degree of u) O(1)
"List all neighbors of u" O(degree of u) O(V)
Good for most real graphs (sparse) small or very dense graphs

V is the number of vertices and E the number of edges. Real graphs are usually sparse: a road network has millions of intersections, but each one connects to only a handful of roads. An adjacency matrix for a million vertices would need a trillion cells, so adjacency lists are the default. In Java, a Map<String, List<String>> is an adjacency list, with keys of any type you like.

Java An adjacency-list graph built from input

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The class uses a LinkedHashMap so vertices print in the order they first appeared (LinkedHashMap and LinkedHashSet). The last input line, Rome Vienna, is not connected to the rest: graphs can have several separate pieces, called connected components. You'll count them with DFS shortly. Edit the Input box to build your own network; every algorithm in this lesson uses the same Graph idea.

Breadth-first search explores a graph in rings: first the start vertex, then all its neighbors, then all their unvisited neighbors, and so on, like ripples spreading from a stone dropped in water. It uses a queue (FIFO) of vertices waiting to be explored and a visited set so no vertex is processed twice.

  1. Put the start vertex in the queue and mark it visited.
  2. While the queue isn't empty: take the vertex at the front, and for each neighbor that isn't visited yet, mark it visited and add it to the back of the queue.

Because the queue processes vertices in the order they were discovered, BFS visits everything at distance 1 before anything at distance 2. That means the first time BFS reaches a vertex, it has found the fewest edges needed to get there.

Java BFS levels and a shortest path

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The trace prints the queue after each visit, so you can watch the rings form. Lisbon is at distance 0; Madrid at 1; Paris and Lyon at 2; Brussels, Berlin and Milan at 3; and so on. Each vertex enters the queue exactly once.

To rebuild a path, BFS stores each vertex's parent: the vertex it was discovered from. Following parents from Vienna back to Lisbon gives the route in reverse; adding each step to the front of a list fixes the order. Vienna is reached through Lyon and Milan: Lisbon, Madrid, Lyon, Milan, Vienna is 4 edges. The route through Paris, Berlin and Prague needs 5, so BFS never picks it: by the time Prague is visited, Vienna is already marked.

Three details are easy to get wrong:

  • Mark a vertex visited when you add it to the queue, not when you take it out. Otherwise the same vertex can be queued several times by different neighbors, which wastes work and, in dense graphs, blows up the queue.
  • Use ArrayDeque with offer/poll, never ArrayList.remove(0), which is O(n) per call.
  • BFS shortest paths only count edges. If edges have different lengths, the path with the fewest edges isn't necessarily the shortest in kilometers. That's what Dijkstra's algorithm, below, is for.

BFS runs in O(V + E): every vertex is queued once, and every adjacency list is scanned once.

BFS on a grid: escaping a maze

Many graphs are never stored as a map at all. In a grid maze, each open cell is a vertex, and its up/down/left/right open neighbors are its edges; you compute neighbors on the fly. This is an implicit graph, and BFS works on it unchanged.

Java Shortest way out of a maze with BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The Cell record is a perfect value type for coordinates: equals and hashCode come for free. Arrays replace the maps here because cells have natural integer indexes, and dist == -1 doubles as "not visited". Draw your own maze in the Input box (# walls, . open, S start, E exit); wall off the exit to see the "No way out!" case.

Depth-first search takes the opposite strategy: follow one path as far as it goes, and only when you hit a dead end, back up to the most recent vertex with unexplored neighbors. It's how you'd explore a cave with a ball of string. DFS is naturally recursive: to explore a vertex, mark it visited, then explore each unvisited neighbor.

DFS doesn't find shortest paths, but it's the tool for questions about structure: Is everything connected? How many separate pieces are there? Is there a cycle? In what order can these tasks run?

Java Recursive DFS and connected components

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The indented trace shows DFS diving deep: from A it goes to B, then D, then (from D) C, then backs up to D and continues to E. Only after A's whole component is finished does the outer loop find F, an unvisited vertex, and start a new search. Each fresh start is a new connected component, which is how the program finds four of them: Aโ€“E, Fโ€“G, the triangle Hโ€“Iโ€“J and the lonely K.

The iterative version replaces the call stack with an explicit ArrayDeque used as a stack. It visits vertices in the same order as the recursive one because it pushes neighbors in reverse. Notice it marks vertices visited when they're popped, not pushed, and skips duplicates with visited.add(v), which returns false for a vertex that's already in the set. That's correct for DFS order; the BFS rule "mark when queued" is about not queuing duplicates, and DFS tolerates them on its stack.

Why bother with the iterative version? Each recursive call uses a stack frame, and the default thread stack holds somewhere between a few thousand and a few tens of thousands of frames for a method like this, depending on frame size and JVM settings. A DFS down a path of a million vertices (a long chain, or a big grid) throws StackOverflowError. The explicit stack lives on the heap and can grow as large as memory allows.

BFS DFS
Data structure queue stack (or recursion)
Explores ring by ring, nearest first one branch to the end, then backtracks
Shortest path (unweighted) yes no
Typical uses fewest hops, levels, nearest match components, cycles, topological order, mazes, backtracking
Time O(V + E) O(V + E)

Topological order: scheduling tasks

In a directed acyclic graph, a topological order lists the vertices so that every edge points forward: each task appears after everything it depends on. Build tools, spreadsheet recalculation and course prerequisite planners all need one. A neat DFS-based method is to add a vertex to the result after all its descendants are finished (post-order) and then reverse. The same search also detects cycles: reaching a vertex that is still "in progress" means you've looped back onto the current path.

Java Build order with DFS and cycle detection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The three enum states are what make cycle detection work. DONE vertices are finished and safe to skip; IN_PROGRESS vertices are on the current recursion path, so reaching one again means the path loops. result.addFirst(v) builds the reversed post-order directly, so no separate reverse step is needed. After adding deploy -> fetch, the search walks fetch, compile, test, package, deploy and then hits fetch while it's still in progress, so it reports the cycle instead of returning a nonsense order.

Weighted shortest paths: Dijkstra's algorithm

When edges have weights, the path with the fewest edges isn't always the cheapest. Driving Lisbon โ†’ Madrid โ†’ Paris might be 1,900 km while a three-hop route is 1,700 km. Dijkstra's algorithm finds the cheapest path from one start vertex to every other vertex, as long as no weight is negative.

The idea generalizes BFS. Instead of a FIFO queue, use a priority queue ordered by the distance found so far, so the algorithm always expands the closest vertex it hasn't finalized yet. When a vertex comes out of the priority queue, its distance is final: any other route would have to go through a vertex that's at least as far away, and with non-negative weights it can't come back cheaper.

  1. Set dist[start] = 0 and every other distance to infinity. Put (start, 0) in the priority queue.
  2. Poll the vertex u with the smallest distance. If that entry is outdated (a shorter distance was already found), skip it.
  3. For each edge u โ†’ v with weight w: if dist[u] + w < dist[v], you've found a shorter way to v. Update dist[v], record u as v's parent, and add (v, dist[v]) to the queue. This step is called relaxing the edge.
  4. Repeat until the queue is empty.
Java Dijkstra with a PriorityQueue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Read the trace from the top. Lisbon is finalized at 0, which relaxes Madrid (625) and Porto (313). Porto is closer, so it's finalized next and offers Bilbao at 313 + 690 = 1,003. Then Madrid is finalized at 625; its road to Bilbao would give 625 + 400 = 1,025, which is worse, so Bilbao keeps 1,003. Madrid does give Barcelona its first distance, 1,245.

Lyon shows the most interesting step. Barcelona, finalized at 1,245, offers Lyon at 1,245 + 640 = 1,885. Later, Bordeaux (1,343) finds a cheaper way: 1,343 + 500 = 1,843. Lyon's distance is updated and a second entry goes into the queue. The cheaper entry comes out first and finalizes Lyon at 1,843; the old 1,885 entry is polled afterwards and skipped as stale.

When a better distance for a vertex is found, the old queue entry isn't removed (Java's PriorityQueue.remove(Object) is O(n)). Instead, a new entry is added, and the outdated one is skipped when it's polled, which is what the skip stale line shows. This lazy deletion is the standard way to write Dijkstra in Java. The distance check is essential: without it, stale entries would relax edges again with wrong distances.

The running time is O((V + E) log V) with a binary heap: each edge can add one queue entry, and each queue operation costs O(log V).

Dijkstra's algorithm gives wrong answers if any edge weight is negative, because a finalized distance could later be undercut. For graphs with negative weights (but no negative cycles), use the Bellmanโ€“Ford algorithm, which is slower at O(V ยท E). For grids or maps where you can estimate the remaining distance, the A* algorithm is Dijkstra plus a heuristic and usually explores far fewer vertices.

Backtracking

Some problems aren't about walking a graph you've been given; they're about searching through choices. Which order should these items go in? Which subset adds up to 100? Where can eight queens stand on a chessboard so that none attacks another? Backtracking solves them with a recursive pattern you can apply almost mechanically:

Java
void backtrack(State partial) {
    if (isComplete(partial)) {
        record(partial);                 // a full solution
        return;
    }
    for (Choice c : choicesFor(partial)) {
        if (isValid(partial, c)) {
            apply(partial, c);           // choose
            backtrack(partial);          // explore
            undo(partial, c);            // un-choose: restore the state exactly
        }
    }
}

Choose, explore, un-choose. Each recursive level makes one decision; the "undo" step returns the shared state to exactly what it was, so the next choice starts from a clean slate. The search is really a DFS over an invisible tree of partial solutions, and pruning (the isValid check) cuts off whole branches that can never lead to a solution.

Permutations and subsets

A permutation of [A, B, C] is any ordering of all three letters; there are 3! = 6. At each level, choose any letter not used yet. For subsets, each element has just two choices: leave it out or put it in, giving 2โฟ subsets.

Java Permutations and subsets by backtracking

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The un-choose lines are the whole trick. permute shares one StringBuilder and one used array across every call; deleting the last character and clearing used[i] restore them exactly. Remove used[i] = false; and run it again: once a letter is marked used, it never becomes available, and you get only one permutation.

The subset search adds two lessons. First, List.copyOf(chosen) stores a snapshot. Adding chosen itself would store the same live list over and over, and since every addition is undone, you'd end up with a list of empty lists. Second, remaining < 0 prunes: once the sum overshoots, no further coins can fix it, so the whole branch is skipped. (removeLast() comes from Java 21's sequenced collections.)

Backtracking is exponential by nature: n! permutations and 2โฟ subsets grow fast. 10! is already 3,628,800. Pruning is what makes real searches practical.

N-Queens

Place N queens on an N ร— N chessboard so that no two share a row, column or diagonal. Since each row holds exactly one queen, the recursion places one queen per row and tries every column. A column is valid if no earlier queen is in the same column or on either diagonal. Two squares (r1, c1) and (r2, c2) share a diagonal when r1 - c1 == r2 - c2 (falling diagonal) or r1 + c1 == r2 + c2 (rising diagonal), so three boolean arrays make every check O(1).

Java N-Queens with O(1) safety checks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The famous answer for the standard board is 92 solutions. The "placements tried" column shows pruning at work: for N = 8, the search places a queen only about two thousand times, while trying every arrangement of one queen per row would mean 8โธ, almost 17 million boards. Each check against the three arrays rejects a square instantly, and a rejected square cuts off every board that would have extended it.

The + n - 1 in the falling-diagonal index shifts row - col (which ranges from โˆ’(nโˆ’1) to nโˆ’1) into a valid array index. The fields are static for brevity; in a larger program you'd put the state in an object.

Recursion or iteration?

All the recursive algorithms here can be written with an explicit stack, and sometimes they should be:

  • Recursion is clearest when the problem is recursive: trees, DFS, divide and conquer, backtracking. The call stack stores your progress for free.
  • Depth is the danger. Recursion depth equals the longest path, not the number of vertices. Backtracking over 8 rows is 8 frames deep, and a balanced tree of a million nodes is about 20 deep, both harmless. A DFS along a 100,000-vertex chain needs 100,000 frames and overflows. Use an explicit ArrayDeque when depth can grow with the input.
  • Java has no tail-call optimization, so rewriting a method as tail-recursive doesn't save stack space the way it does in some functional languages.
  • Memoization (from Recursion) helps when the same subproblem repeats, which turns many exponential searches into polynomial dynamic programming. Backtracking explores different partial states, so it usually can't be memoized, but pruning keeps it fast.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does BFS find the path with the fewest edges in an unweighted graph?

    The FIFO queue explores the graph in rings. The first time a vertex is reached, it is from the nearest ring, so no path with fewer edges exists.
  2. 2. In a grid BFS, what goes wrong if you mark a cell as visited only when it is polled from the queue instead of when it is offered?

    Several neighbors can discover the same cell before it is polled, so it gets queued repeatedly. Distances can still come out right if you check on poll, but the extra work can be large; marking on offer queues each cell exactly once.
  3. 3. A DFS for topological order reaches a vertex whose state is IN_PROGRESS. What does that mean?

    IN_PROGRESS vertices are on the current recursion path. Reaching one again means you followed edges back to a vertex you started from, which is a cycle, so no topological order exists.
  4. 4. Why does the Dijkstra example skip entries whose distance is larger than dist.get(vertex)?

    Instead of removing old entries from the queue (slow), the code adds a new entry when it finds a shorter distance. The old one is ignored when it is eventually polled. This is called lazy deletion.
  5. 5. In the permutation code, what happens if you delete the line used[i] = false;?

    The un-choose step must restore the shared state. Without it, every letter stays marked as used after its first use, so after ABC is built no other branch can choose any letter.

Summary

  • A graph is vertices plus edges (directed or undirected, weighted or not); store sparse graphs as an adjacency list such as Map<String, List<String>>.
  • BFS uses a queue, explores ring by ring in O(V + E), and gives shortest paths by edge count; keep a parent map to rebuild the route, and mark vertices visited when you queue them.
  • Grids and puzzles are implicit graphs: compute neighbors on the fly and use arrays for distances and parents.
  • DFS uses recursion or an explicit stack; it finds connected components, detects cycles and produces a topological order (reversed post-order). Prefer the explicit stack when paths can be very long.
  • Dijkstra's algorithm finds cheapest paths with non-negative weights using a PriorityQueue with lazy deletion, in O((V + E) log V).
  • Backtracking is choose, explore, un-choose; restore shared state exactly, store snapshots of solutions, and prune invalid branches early, as in permutations, subset sums and N-Queens.

Next: Java Cheat Sheet, a dense one-page reference of Java syntax and the APIs you'll use every day.