Skip to content
Tutorials Center
My learning

Topics

Lesson 161 of 171 ยท Data Structures and Algorithms

Graphs, Recursion and Backtracking

Represent graphs in C++ with adjacency lists, explore them with BFS and DFS, find shortest paths with Dijkstra, order tasks topologically and solve N-Queens by backtracking.

A graph is a set of vertices (also called nodes) connected by edges. That simple idea describes a surprising amount of the world: cities joined by roads, people joined by friendships, web pages joined by links, build steps joined by "must happen before", positions in a game joined by legal moves. Once you see a problem as a graph, a small toolbox of algorithms solves it: breadth-first search finds the fewest steps, depth-first search explores everything reachable, Dijkstra's algorithm finds the cheapest route, and topological sort finds an order that respects every dependency.

Many graph algorithms are naturally recursive, and the last part of this lesson takes recursion further with backtracking: building a solution one choice at a time and undoing choices that lead nowhere. That's how you generate every permutation, place eight queens on a chessboard so that none attack each other, or solve a Sudoku.

You should know recursion, std::vector, and the queue and priority_queue adapters. The previous lessons, Data Structures in C++ and Searching and Sorting Algorithms, introduced the Big-O notation used here.

Graph vocabulary

A few terms come up constantly:

  • Directed vs undirected. In an undirected graph, an edge between A and B can be walked both ways (a friendship, a two-way road). In a directed graph, an edge A โ†’ B goes one way only (a link, a one-way street, "A must happen before B").
  • Weighted vs unweighted. A weight is a number on an edge: a distance, a cost, a travel time. Unweighted graphs treat every edge as one step.
  • Neighbors and degree. The neighbors of a vertex are the vertices it has edges to. Its degree is how many there are.
  • Path and cycle. A path is a sequence of vertices joined by edges. A cycle is a path that returns to its start. A directed graph without cycles is a DAG (directed acyclic graph).
  • Connected component. In an undirected graph, a maximal group of vertices that can all reach each other.

We write V for the number of vertices and E for the number of edges. Graph algorithms are measured in both: BFS and DFS run in O(V + E), Dijkstra in O((V + E) log V).

Representing a graph

The two classic representations are:

  • An adjacency matrix: a V ร— V table where cell [u][v] says whether there's an edge (or holds its weight). Checking a specific edge is O(1), but the table takes Vยฒ memory even if there are few edges, and listing a vertex's neighbors costs O(V).
  • An adjacency list: for each vertex, a list of its neighbors. Memory is O(V + E), and listing neighbors costs exactly as many steps as there are neighbors. Real-world graphs are usually sparse (a city has a few roads, not a road to every other city), so adjacency lists are the default.

In C++, an adjacency list is simply std::vector<std::vector<int>>: vertices are numbered 0 to V โˆ’ 1, and adjacency[u] holds the neighbors of u. For a weighted graph, store pairs or a small Edge struct instead of plain ints. When vertices have names, keep a std::map or std::unordered_map from name to number, plus a vector for the way back, and run the algorithms on the numbers.

C++ Building an adjacency list from named edges

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 std::cin or std::getline), it gets the next line from this box.

Each undirected edge appears twice in the adjacency list, once in each endpoint's list, so the lists hold 2E entries in total. The matrix makes the trade-off visible: 100 cells for just 9 edges. Edit the Input box to add your own edges, or add a weight column for the next sections.

Breadth-first search (BFS)

Breadth-first search explores a graph in rings: first the start vertex, then all its neighbors, then all their unvisited neighbors, and so on. It uses a queue (first in, first out), which is what makes it go level by level:

  1. Mark the start as visited with distance 0 and push it into the queue.
  2. While the queue isn't empty: pop the front vertex u; for each neighbor v not visited yet, mark it visited, set distance[v] = distance[u] + 1, remember parent[v] = u, and push it.

Because vertices are discovered in order of distance, the first time BFS reaches a vertex is along a shortest path (fewest edges). The parent array records how each vertex was reached, so walking it backwards from the target and reversing gives the path itself. Each vertex is queued once and each edge examined once or twice: O(V + E).

C++ BFS: degrees of separation

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 std::cin or std::getline), it gets the next line from this box.

The trace shows the rings: Ava (distance 0), then Ben and Cleo (1), then Dev and Gus (2), then Eli and Hana (3), and finally Fay (4). Ivo is never discovered, so his distance stays โˆ’1: he's in a different connected component.

Mark vertices as visited when you push them, not when you pop them. If you wait until popping, a vertex reachable from several queued vertices gets pushed several times, which wastes work and, in dense graphs, can blow up the queue.

Grids are graphs too

Many puzzles hide a graph inside a grid: each open cell is a vertex, and it has edges to its open neighbors up, down, left and right. You don't need to build an adjacency list at all; the neighbors are computed on the fly from the coordinates. BFS then finds the shortest route through a maze.

C++ Shortest path through 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 std::cin or std::getline), it gets the next line from this box.

Change the walls in the Input box and run it again. If you block every route, BFS empties the queue without reaching E and the program reports that there's no way out.

Depth-first search (DFS)

Depth-first search does the opposite of BFS: it follows one path as far as it can, and only when it hits a dead end does it back up to the most recent vertex with an unexplored neighbor. Recursion expresses that perfectly, because the call stack remembers the way back:

C++
void dfs(int u, const Graph& g, std::vector<bool>& visited) {
    visited[u] = true;
    for (int v : g[u]) {
        if (!visited[v]) {
            dfs(v, g, visited);      // go deeper; returning = backing up
        }
    }
}

DFS doesn't find shortest paths, but it's the foundation of many other algorithms: finding connected components, detecting cycles, topological sorting, finding bridges and articulation points, and solving mazes or puzzles where any solution will do. It runs in O(V + E), like BFS.

The recursive version has one serious practical limit: each vertex on the current path is one stack frame. A path through a million vertices (a long chain, a big grid) can overflow the call stack. The fix is an explicit stack, a std::vector<int> used as a stack, which lives on the heap and can grow as large as memory allows.

C++ DFS: recursive, iterative 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 std::cin or std::getline), it gets the next line from this box.

The indentation of the recursive trace is the call stack: enter 3 happens while 0 and 1 are still in progress, and leave 1 comes only after everything below 1 is finished. The component loop is a pattern worth memorizing: start a new search from every vertex that no previous search reached, and count how many searches you needed.

The iterative version marks vertices when it pops them rather than when it pushes them, so a vertex can sit on the stack twice; the if (visited[u]) continue; line skips the duplicates. That keeps the visiting order identical to the recursive version.

Dijkstra's shortest paths

BFS finds the path with the fewest edges. When edges have different weights, such as road lengths, the route with the fewest roads isn't necessarily the shortest. Dijkstra's algorithm solves this for non-negative weights:

  1. Set every distance to infinity, except the start, which is 0.
  2. Repeatedly take the unfinished vertex with the smallest known distance; its distance is now final.
  3. Relax its edges: for each edge u โ†’ v with weight w, if distance[u] + w < distance[v], you've found a shorter way to v, so update it and remember parent[v] = u.

"Take the smallest" is the job of a min-priority queue. std::priority_queue is a max-heap by default, so we store (distance, vertex) pairs with std::greater<> as the comparator to turn it into a min-heap. The standard queue can't lower a key in place, so when a distance improves we simply push a new pair; the outdated pair is skipped when it's eventually popped (the check if (d > dist[u]) continue;). This "lazy deletion" version runs in O((V + E) log V).

C++ Dijkstra with std::priority_queue

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 std::cin or std::getline), it gets the next line from this box.

Look at Summit: the direct-looking route Harbor โ†’ Delta โ†’ Summit costs 14 + 9 = 23 km, but Dijkstra finds Harbor โ†’ Ridge โ†’ Delta โ†’ Summit at 9 + 2 + 9 = 20 km. Likewise Delta itself is cheaper through Ridge (11 km) than by its direct road (14 km), which is why a stale (14, Delta) entry gets skipped in the trace.

Things professionals keep in mind:

  • Negative weights break Dijkstra. Once a vertex is settled, the algorithm assumes nothing can make it cheaper, and a negative edge could. Use the Bellmanโ€“Ford algorithm (O(VยทE)) for graphs with negative weights; it also detects negative cycles.
  • Overflow. dist[u] + km overflows if dist[u] is still infinity. That can't happen here, because only settled vertices are relaxed, but code that relaxes edges from unreached vertices must check first. With large weights, use long long.
  • Early exit. If you only need one target, stop as soon as it's settled.
  • Unweighted graphs don't need Dijkstra: plain BFS is simpler and faster. For graphs with weights 0 and 1 only, a deque-based "0-1 BFS" is O(V + E).

Topological sort

A topological order of a directed graph lists the vertices so that every edge points forward: if a โ†’ b, then a comes before b. It answers "in what order can I do these tasks?" for build systems, course prerequisites, spreadsheet recalculation and package installers. It exists exactly when the graph has no cycles, so the same algorithm doubles as a cycle detector.

Kahn's algorithm works with in-degrees (the number of edges pointing into each vertex):

  1. Count every vertex's in-degree. Vertices with in-degree 0 have no prerequisites: put them in a queue.
  2. Repeatedly take a vertex from the queue and append it to the order. "Remove" its outgoing edges by decrementing each target's in-degree; any target that reaches 0 is now ready, so queue it.
  3. If the order ends up shorter than the number of vertices, the leftover vertices are stuck in a cycle.
C++ Build order with Kahn's algorithm

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 std::cin or std::getline), it gets the next line from this box.

A graph usually has many valid topological orders; "generate code" could just as well come first. Kahn's algorithm with a plain queue gives one of them. If you need a specific one, such as the alphabetically smallest, use a std::priority_queue (min-heap) for ready instead.

There's also a DFS-based method: run DFS from every unvisited vertex and append each vertex to a list when DFS leaves it (post-order). Reversing that list gives a topological order, because a vertex is only left after everything that depends on it has been left. Detecting a cycle with DFS requires three states per vertex (unvisited, in progress, done): reaching an "in progress" vertex again means you've found a cycle.

Backtracking

Backtracking is recursion used to search through choices. You build a candidate solution one decision at a time, and after each decision you recurse to make the next one. When a partial solution can't possibly lead to a valid answer, or when you've completed one, you undo the last decision and try the next option. The skeleton is always the same:

C++
void solve(State& state) {
    if (is_complete(state)) {
        record(state);
        return;
    }
    for (const auto& choice : options(state)) {
        if (!is_allowed(state, choice)) {
            continue;                // prune: don't explore hopeless branches
        }
        apply(state, choice);        // choose
        solve(state);                // explore
        undo(state, choice);         // un-choose
    }
}

DFS is backtracking on a graph; here, the "graph" is the tree of all possible partial solutions, which is far too big to build, so you generate it while you walk it. Undoing the change after each recursive call is what lets one shared state object serve the whole search without copying it at every level.

Generating permutations

To list every ordering of n items, choose which item goes in the first position, then recursively order the rest. A used array tracks which items are already placed:

C++ Permutations 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 std::cin or std::getline), it gets the next line from this box.

The trace shows the search tree: choosing A first leads to "AB" then "ABC", and after recording it the recursion backs up, un-chooses C and B, and tries C second ("AC", then "ACB"). There are n! permutations (7! = 5,040 for seven letters), so any algorithm that lists them all is at least O(n ยท n!); backtracking can't avoid that, but it never builds anything twice.

The duplicate rule is a classic trick: after sorting, identical letters sit next to each other, and we only allow the second A to be used if the first A already is. That forces identical letters to always appear in the same relative order, so each distinct arrangement is generated exactly once.

The N-Queens puzzle

Place N chess queens on an N ร— N board so that no two attack each other: no two in the same row, column or diagonal. Trying every way to put 8 queens on 64 squares would mean billions of boards. Backtracking makes it fast by pruning early:

  • Put exactly one queen in each row, so rows never conflict. That leaves N choices per row.
  • Before placing a queen, check its column and both diagonals. Squares on the same "down-right" diagonal share row - col; squares on the same "down-left" diagonal share row + col. Three std::vector<bool> arrays make each check O(1).
  • If no column in the current row is safe, return immediately: the whole subtree below this partial board is skipped.
C++ N-Queens: count all solutions and draw one

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 std::cin or std::getline), it gets the next line from this box.

The output confirms the famous numbers: 92 solutions for the 8 ร— 8 board and 724 for 10 ร— 10, while 2 ร— 2 and 3 ร— 3 have none. The call counts show how well pruning works: for N = 8 the search makes about 2,000 calls instead of examining the 8โธ โ‰ˆ 16.8 million ways to put one queen in each row. Better pruning means a smaller search tree, and that's where the real gains in backtracking come from. The same pattern solves Sudoku (cells instead of rows, digits instead of columns), subset-sum problems, crossword fillers and many scheduling puzzles.

Recursion: when to use it and when not

The algorithms in this lesson show both sides of recursion:

  • Recursion fits when the problem is self-similar and the depth stays small: backtracking (depth = number of decisions, such as N for N-Queens), divide and conquer (depth log n), and DFS on graphs you know are shallow.
  • Use an explicit stack or queue when the depth can grow with the input: DFS on large or chain-like graphs, flood fill on big images, tree walks over unbalanced trees. Default stack sizes are usually 1โ€“8 MB, so a few hundred thousand nested calls can crash a program, and C++ gives no clean error when that happens.
  • Pass big state by reference and undo changes after each call, as the backtracking examples do. Copying the board or the partial permutation at every level turns a fast search into a slow one.
  • Recursive lambdas are possible too: C++23's explicit object parameter ("deducing this") lets a lambda call itself, as in auto dfs = [&](this auto& self, int u) -> void { ... self(v); ... };. A named function is usually clearer.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. You need the route with the fewest flights between two airports, where every flight counts as one step. Which algorithm fits best?

    In an unweighted graph BFS discovers vertices in order of distance, so the first time it reaches the target is along a path with the fewest edges. DFS can find a much longer path first.
  2. 2. Why does the Dijkstra example contain if (d > dist[u]) continue;?

    When a vertex's distance improves, a new pair is pushed and the old one stays in the queue. When the stale pair is popped later, its distance is larger than the recorded one and it's skipped.
  3. 3. Kahn's algorithm processes 6 of a graph's 8 vertices and then the queue is empty. What does that tell you?

    A vertex enters the queue only when its in-degree drops to 0. Vertices on a cycle (and those depending on it) never reach 0, so a shorter-than-V order means there's a cycle.
  4. 4. In the N-Queens solver, two squares (r1, c1) and (r2, c2) are on the same down-right diagonal exactly when...

    Moving one square down-right adds 1 to both the row and the column, so row - col stays constant along that diagonal. row + col is constant along the other diagonal.
  5. 5. A recursive DFS crashes on a graph that is one long chain of 2,000,000 vertices, but works on small graphs. What is the most likely cause and fix?

    Recursion depth equals the path length, and two million nested calls exceed the default stack size. An explicit std::vector used as a stack lives on the heap and can grow as needed.

Summary

  • A graph is vertices plus edges, directed or undirected, weighted or not. Store sparse graphs as adjacency lists (std::vector<std::vector<int>>); map names to numbers with a hash map.
  • BFS uses a queue, explores level by level and finds shortest paths in unweighted graphs in O(V + E); a parent array reconstructs the path. Grids are graphs whose neighbors you compute on the fly.
  • DFS goes deep first, recursively or with an explicit stack, in O(V + E); it finds connected components and underlies cycle detection and topological sorting. Use the explicit stack when depth can be large.
  • Dijkstra finds cheapest paths with non-negative weights using a min-priority_queue and lazy deletion, in O((V + E) log V).
  • Topological sort (Kahn's algorithm) orders tasks so every dependency comes first, and detects cycles when vertices are left over.
  • Backtracking is choose, explore, un-choose. It generates permutations and solves N-Queens; pruning hopeless branches early is what makes it fast.

Next: C++ Cheat Sheet, a dense one-page reference of everything you've learned in this course.