Depth-First Search (DFS): Islands, Cycles and Code

Explore a maze with a stick of chalk and one rule: keep walking into corridors you have not chalked yet, and at a dead end walk back to the last junction with an unchalked corridor. You will see every room you can reach, each once. That is depth-first search (DFS): follow one path as deep as it goes, then backtrack and try the next. Where breadth-first search spreads out in rings, DFS dives.

DFS is behind counting islands, connected components, cycle detection and ordering tasks. It is the recursion of backtracking with one change: a vertex, once visited, stays visited. It assumes you know how a graph is stored.

Why a traversal must remember where it has been

A walk that just keeps moving to neighbours never ends on a graph with a cycle. Marking only the current path, and unmarking on the way back, does finish, but it explores every simple path rather than every vertex: about 2.4 × 10¹¹ of them from one start in a graph of 15 vertices all joined to each other. DFS never unmarks, so each vertex is entered once and each edge looked at from both ends: a few hundred steps.

The idea: go deep, then backtrack

• When you arrive at a vertex, mark it visited.
• Take its neighbours one at a time. For each one not visited yet, go there at once and finish that whole branch before looking at the next.
• When no unvisited neighbour is left, return to the vertex you came from: the backtrack.

Recursion does the bookkeeping: the call stack always holds the path from the start to the vertex being explored.

1. Depth-first search follows one path as deep as it goes before trying another. dfs(A) is called: A is discovered 1st and pushed on the call stack.
2. In dfs(A), B is unvisited, so dfs(B) is pushed on top and B is discovered 2nd. A's other neighbours wait until B's whole branch is finished.
3. In dfs(B), D is unvisited, so dfs(D) is pushed on top and D is discovered 3rd. The stack always holds the path from A down to the node being explored.
4. In dfs(D), E is unvisited, so dfs(E) is pushed on top and E is discovered 4th. The path is now A → B → D → E.
5. E–B leads back to B, still on the stack: a back edge, which means the graph has a cycle, so it is not followed. Nothing unvisited is left around E: dfs(E) is popped and the search backtracks to D.
6. Back in dfs(D), nothing unvisited is left: dfs(D) is popped and the search backtracks to B.
7. Back in dfs(B), E is already finished (reached through D), so nothing unvisited is left: dfs(B) is popped and the search backtracks to A.
8. Back in dfs(A), C is unvisited, so dfs(C) is pushed on top and C is discovered 5th. The search goes deep again from here.
9. In dfs(C), F is unvisited, so dfs(F) is pushed on top and F is discovered 6th. That is every node found, but the open calls still have to return.
10. F's only neighbour is C, its caller, so dfs(F) returns at once and the search backtracks to C.
11. Back in dfs(C), nothing unvisited is left: dfs(C) is popped and the search backtracks to A.
12. dfs(A) returns and the stack is empty. Discovery order: A, B, D, E, C, F; the teal edges are the calls made, the dashed one the back edge. Each node and edge is handled once: O(V + E).

Why it works

No vertex is visited twice, because dfs(v) is called only when v is unvisited and its first act is to mark it. And every reachable vertex is visited. Suppose one were missed: on a path from the start to it, take the first unvisited vertex x and the vertex w before it. dfs(w) ran and looped over every neighbour of w, so it would have called dfs(x), a contradiction. Each call reads one adjacency list once: O(V + E) in all, the same as BFS.

Recursion or an explicit stack

The same search works with a stack you manage yourself, which is what you need when recursion would go too deep. Pushing the neighbours in reverse order makes the first one come off first, so the order matches the recursive one.

1. The stack starts with A, unmarked. A vertex is marked when it is popped, which is the moment the recursive version would enter it.
2. Pop A and mark it 1st. Its unvisited neighbours B and C are pushed in reverse order, so B, the first, ends on top and comes off next, just as recursion would take it first.
3. Pop B, mark it 2nd, push D and E. The search goes deeper from here, as recursion would.
4. Pop D, mark it 3rd, push E. E is now on the stack twice: it was pushed earlier but not yet popped, and is only marked when it is.
5. Pop E and mark it 4th. Every neighbour is already visited, so nothing is pushed: this is where recursion would return.
6. Pop E: already visited, because it was pushed twice, so it is skipped. Marking on pop is what keeps the true depth-first order, at the price of extra entries: the stack can hold O(E) of them.
7. Pop C, mark it 5th, push F. The search goes deeper from here, as recursion would.
8. Pop F and mark it 6th. Every neighbour is already visited, so nothing is pushed: this is where recursion would return.
9. The stack is empty. The visiting order, A B D E C F, is exactly the recursive one, and no call stack was used, so depth is limited only by memory.

Marking on push instead, as BFS does, still reaches everything, which is fine for counting islands, but the order stops being truly depth-first, and cycle detection depends on it.

Connected components and islands

One DFS visits exactly one connected component. Loop over every vertex and start a new search from each one still unvisited: each start is a new component, and since marks are never cleared the loop is still O(V + E), as in Number of Provinces. On a grid, each search from unvisited land sweeps up one island; the marks can live in the grid itself, by sinking each cell as you visit it.

1. Land is 1 and water 0. The outer loop scans row by row; each land cell that no earlier search has sunk starts a new island, and sink() floods all of it.
2. Island 1 starts at (0, 0). sink() tries up, down, left, right, diving at once into each land cell it finds: (0, 0), (1, 0), (1, 1), (0, 1), numbered in the order reached. Each turns to water before the dive goes on.
3. Island 2 starts at (1, 3), the first land cell left, and sink() reaches 3 cells. Sunk islands are now water, so the scan passes over them without starting anything.
4. Island 3 starts at (3, 1). After (4, 0), a dead end, the calls return to (4, 1), which still has a neighbour to try: (4, 2). That return is the backtrack.
5. Island 4 is the single cell (4, 4): the cells beside it are water, and cells only join along a side, never at a corner.
6. The scan ends with 4 islands, the largest 4 cells. Every cell was scanned once and every land cell sunk once, so the whole count is O(rows × columns).

Check that the cell is inside the grid and is land before touching it, and sink it before the recursive calls; sink it afterwards and two neighbours call each other until the stack overflows.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int DR[4] = {-1, 1, 0, 0};  // up, down, left, right
const int DC[4] = {0, 0, -1, 1};
vector<string> grid = {"11000", "11011", "00001", "01000", "11101"};
int rows = grid.size(), cols = grid[0].size();

// Sinks the island that contains (r, c) and returns how many cells it had.
int sink(int r, int c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return 0;  // off the grid, water, or sunk
    grid[r][c] = '0';  // mark before going deeper, or the neighbours would call back here forever
    int size = 1;
    for (int d = 0; d < 4; d++) size += sink(r + DR[d], c + DC[d]);
    return size;
}

int main() {
    int islands = 0, largest = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {  // land that no earlier search sank: a new island
                islands++;
                int size = sink(r, c);
                largest = max(largest, size);
                cout << "Island " << islands << " found at (" << r << ", " << c << "), size " << size << "\n";
            }
        }
    }
    cout << "Number of islands: " << islands << "\n";
    cout << "Largest island: " << largest << " cells\n";
    return 0;
}

public class Main {
    static final int[] DR = {-1, 1, 0, 0}; // up, down, left, right
    static final int[] DC = {0, 0, -1, 1};
    static char[][] grid;
    static int rows, cols;

    // Sinks the island that contains (r, c) and returns how many cells it had.
    static int sink(int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return 0; // off the grid, water, or sunk
        grid[r][c] = '0'; // mark before going deeper, or the neighbours would call back here forever
        int size = 1;
        for (int d = 0; d < 4; d++) size += sink(r + DR[d], c + DC[d]);
        return size;
    }

    public static void main(String[] args) {
        String[] lines = {"11000", "11011", "00001", "01000", "11101"};
        rows = lines.length;
        cols = lines[0].length();
        grid = new char[rows][];
        for (int r = 0; r < rows; r++) grid[r] = lines[r].toCharArray();

        int islands = 0, largest = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') { // land that no earlier search sank: a new island
                    islands++;
                    int size = sink(r, c);
                    largest = Math.max(largest, size);
                    System.out.println("Island " + islands + " found at (" + r + ", " + c + "), size " + size);
                }
            }
        }
        System.out.println("Number of islands: " + islands);
        System.out.println("Largest island: " + largest + " cells");
    }
}

DR = [-1, 1, 0, 0]  # up, down, left, right
DC = [0, 0, -1, 1]
grid = [list(row) for row in ["11000", "11011", "00001", "01000", "11101"]]
rows, cols = len(grid), len(grid[0])


def sink(r, c):
    """Sink the island that contains (r, c) and return how many cells it had."""
    if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
        return 0  # off the grid, water, or sunk
    grid[r][c] = "0"  # mark before going deeper, or the neighbours would call back here forever
    size = 1
    for d in range(4):
        size += sink(r + DR[d], c + DC[d])
    return size


islands = 0
largest = 0
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == "1":  # land that no earlier search sank: a new island
            islands += 1
            size = sink(r, c)
            largest = max(largest, size)
            print(f"Island {islands} found at ({r}, {c}), size {size}")
print(f"Number of islands: {islands}")
print(f"Largest island: {largest} cells")

const DR = [-1, 1, 0, 0]; // up, down, left, right
const DC = [0, 0, -1, 1];
const grid = ["11000", "11011", "00001", "01000", "11101"].map((row) => row.split(""));
const rows = grid.length;
const cols = grid[0].length;

// Sinks the island that contains (r, c) and returns how many cells it had.
function sink(r, c) {
  if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") return 0; // off the grid, water, or sunk
  grid[r][c] = "0"; // mark before going deeper, or the neighbours would call back here forever
  let size = 1;
  for (let d = 0; d < 4; d++) size += sink(r + DR[d], c + DC[d]);
  return size;
}

let islands = 0;
let largest = 0;
for (let r = 0; r < rows; r++) {
  for (let c = 0; c < cols; c++) {
    if (grid[r][c] === "1") {
      // land that no earlier search sank: a new island
      islands++;
      const size = sink(r, c);
      largest = Math.max(largest, size);
      console.log(`Island ${islands} found at (${r}, ${c}), size ${size}`);
    }
  }
}
console.log(`Number of islands: ${islands}`);
console.log(`Largest island: ${largest} cells`);

Island 1 found at (0, 0), size 4
Island 2 found at (1, 3), size 3
Island 3 found at (3, 1), size 4
Island 4 found at (4, 4), size 1
Number of islands: 4
Largest island: 4 cells

Cycle detection

In an undirected graph the vertex you came from is always a visited neighbour. Any other visited neighbour means a second route to it, so a cycle exists when DFS meets a visited neighbour that is not its parent, as Graph Valid Tree checks.

On a directed graph that rule fails: two arrows can meet at a vertex with no way back. What matters is whether the vertex met is still on the current path, so each vertex is white (not visited), grey (its call still running) or black (finished).

1. Graph 1 is a diamond: two routes from 0 meet at 3, but nothing leads back. dfs(0) colours 0 grey, meaning it is on the current path.
2. 0 → 1 leads to a white vertex, so dfs(1) starts and 1 turns grey. The grey vertices are always the path from the start: 0 → 1.
3. 1 → 3: 3 is white, so it turns grey too, and the path is 0 → 1 → 3.
4. 3 has no outgoing edge left to try, so it finishes and turns black, and so does 1. Black means everything reachable from it has been explored.
5. Back in dfs(0), the next edge 0 → 2 leads to white 2, which turns grey.
6. 2 → 3 meets 3 a second time, but 3 is black: finished, with no way back to the current path. Not a cycle, although a plain visited flag would say it was.
7. 2 and 0 finish. No edge ever met a grey vertex, so graph 1 has no cycle; the vertices finished in the order 3, 1, 2, 0.
8. Graph 2 has the edge 3 → 1. The search runs 0 → 1 → 2 → 3 and every vertex it enters turns grey: all 4 are on the current path, none finished.
9. 3 → 1 meets a grey vertex: 1 is still on the path, waiting for its call to return, so 1 → 2 → 3 → 1 is a cycle. An edge to a grey vertex is a back edge, and it always closes a cycle.

An edge to a grey vertex is a back edge and always closes a cycle. An edge to a black vertex never does: if any route led from it back to the current path, DFS would already have found that route while exploring it. And no cycle slips past: on any cycle, the first vertex discovered stays grey while everything reachable from it is explored, including the vertex just before it on the cycle, whose edge then finds it grey.

The program prints the cycle by walking parent links back from the back edge, and starts from every white vertex, since one start may not reach a cycle.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int WHITE = 0, GREY = 1, BLACK = 2;  // unvisited, on the current path, finished
vector<vector<int>> adj;
vector<int> colour, parent, finishOrder, cycle;

// Returns true as soon as an edge leads back to a grey vertex.
bool dfs(int u) {
    colour[u] = GREY;
    for (int v : adj[u]) {
        if (colour[v] == GREY) {  // v is on the current path: this back edge closes a cycle
            for (int x = u; x != v; x = parent[x]) cycle.push_back(x);
            cycle.push_back(v);
            reverse(cycle.begin(), cycle.end());
            cycle.push_back(v);
            return true;
        }
        if (colour[v] == WHITE) {
            parent[v] = u;
            if (dfs(v)) return true;
        }
        // BLACK: finished earlier with no way back to the path, so skip it
    }
    colour[u] = BLACK;
    finishOrder.push_back(u);  // exit order
    return false;
}

void report(const string& name, int n, const vector<vector<int>>& edges) {
    adj.assign(n, vector<int>());
    for (const vector<int>& e : edges) adj[e[0]].push_back(e[1]);  // directed: stored from the tail only
    colour.assign(n, WHITE);
    parent.assign(n, -1);
    finishOrder.clear();
    cycle.clear();
    bool found = false;
    for (int u = 0; u < n && !found; u++) {
        if (colour[u] == WHITE) found = dfs(u);  // every vertex, not only 0
    }
    if (found) {
        cout << name << ": cycle";
        for (size_t i = 0; i < cycle.size(); i++) cout << (i > 0 ? " -> " : " ") << cycle[i];
        cout << "\n";
    } else {
        cout << name << ": no cycle\nFinish order:";
        for (int u : finishOrder) cout << " " << u;
        cout << "\nTopological order:";
        for (int i = n - 1; i >= 0; i--) cout << " " << finishOrder[i];
        cout << "\n";
    }
}

int main() {
    report("Graph 1", 4, {{0, 1}, {0, 2}, {1, 3}, {2, 3}});
    report("Graph 2", 4, {{0, 1}, {1, 2}, {2, 3}, {3, 1}});
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    static final int WHITE = 0, GREY = 1, BLACK = 2; // unvisited, on the current path, finished
    static List<List<Integer>> adj;
    static int[] colour, parent;
    static List<Integer> finishOrder, cycle;

    // Returns true as soon as an edge leads back to a grey vertex.
    static boolean dfs(int u) {
        colour[u] = GREY;
        for (int v : adj.get(u)) {
            if (colour[v] == GREY) { // v is on the current path: this back edge closes a cycle
                for (int x = u; x != v; x = parent[x]) cycle.add(x);
                cycle.add(v);
                Collections.reverse(cycle);
                cycle.add(v);
                return true;
            }
            if (colour[v] == WHITE) {
                parent[v] = u;
                if (dfs(v)) return true;
            }
            // BLACK: finished earlier with no way back to the path, so skip it
        }
        colour[u] = BLACK;
        finishOrder.add(u); // exit order
        return false;
    }

    static void report(String name, int n, int[][] edges) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]); // directed: stored from the tail only
        colour = new int[n]; // every vertex starts WHITE (0)
        parent = new int[n];
        Arrays.fill(parent, -1);
        finishOrder = new ArrayList<>();
        cycle = new ArrayList<>();
        boolean found = false;
        for (int u = 0; u < n && !found; u++) {
            if (colour[u] == WHITE) found = dfs(u); // every vertex, not only 0
        }
        StringBuilder line = new StringBuilder(name + ":");
        if (found) {
            line.append(" cycle");
            for (int i = 0; i < cycle.size(); i++) line.append(i > 0 ? " -> " : " ").append(cycle.get(i));
            System.out.println(line);
        } else {
            System.out.println(line.append(" no cycle"));
            StringBuilder finish = new StringBuilder("Finish order:");
            for (int u : finishOrder) finish.append(" ").append(u);
            System.out.println(finish);
            StringBuilder topo = new StringBuilder("Topological order:");
            for (int i = n - 1; i >= 0; i--) topo.append(" ").append(finishOrder.get(i));
            System.out.println(topo);
        }
    }

    public static void main(String[] args) {
        report("Graph 1", 4, new int[][] {{0, 1}, {0, 2}, {1, 3}, {2, 3}});
        report("Graph 2", 4, new int[][] {{0, 1}, {1, 2}, {2, 3}, {3, 1}});
    }
}

WHITE, GREY, BLACK = 0, 1, 2  # unvisited, on the current path, finished


def report(name, n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)  # directed: stored from the tail only
    colour = [WHITE] * n
    parent = [-1] * n
    finish_order = []
    cycle = []

    def dfs(u):
        """Return True as soon as an edge leads back to a grey vertex."""
        colour[u] = GREY
        for v in adj[u]:
            if colour[v] == GREY:  # v is on the current path: this back edge closes a cycle
                x = u
                while x != v:
                    cycle.append(x)
                    x = parent[x]
                cycle.append(v)
                cycle.reverse()
                cycle.append(v)
                return True
            if colour[v] == WHITE:
                parent[v] = u
                if dfs(v):
                    return True
            # BLACK: finished earlier with no way back to the path, so skip it
        colour[u] = BLACK
        finish_order.append(u)  # exit order
        return False

    found = False
    for u in range(n):
        if colour[u] == WHITE and dfs(u):  # every vertex, not only 0
            found = True
            break
    if found:
        print(f"{name}: cycle {' -> '.join(map(str, cycle))}")
    else:
        print(f"{name}: no cycle")
        print("Finish order:", *finish_order)
        print("Topological order:", *reversed(finish_order))


report("Graph 1", 4, [(0, 1), (0, 2), (1, 3), (2, 3)])
report("Graph 2", 4, [(0, 1), (1, 2), (2, 3), (3, 1)])

const WHITE = 0, GREY = 1, BLACK = 2; // unvisited, on the current path, finished

function report(name, n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) adj[u].push(v); // directed: stored from the tail only
  const colour = new Array(n).fill(WHITE);
  const parent = new Array(n).fill(-1);
  const finishOrder = [];
  const cycle = [];

  // Returns true as soon as an edge leads back to a grey vertex.
  function dfs(u) {
    colour[u] = GREY;
    for (const v of adj[u]) {
      if (colour[v] === GREY) {
        // v is on the current path: this back edge closes a cycle
        for (let x = u; x !== v; x = parent[x]) cycle.push(x);
        cycle.push(v);
        cycle.reverse();
        cycle.push(v);
        return true;
      }
      if (colour[v] === WHITE) {
        parent[v] = u;
        if (dfs(v)) return true;
      }
      // BLACK: finished earlier with no way back to the path, so skip it
    }
    colour[u] = BLACK;
    finishOrder.push(u); // exit order
    return false;
  }

  let found = false;
  for (let u = 0; u < n && !found; u++) {
    if (colour[u] === WHITE) found = dfs(u); // every vertex, not only 0
  }
  if (found) {
    console.log(`${name}: cycle ${cycle.join(" -> ")}`);
  } else {
    console.log(`${name}: no cycle`);
    console.log(`Finish order: ${finishOrder.join(" ")}`);
    console.log(`Topological order: ${finishOrder.slice().reverse().join(" ")}`);
  }
}

report("Graph 1", 4, [[0, 1], [0, 2], [1, 3], [2, 3]]);
report("Graph 2", 4, [[0, 1], [1, 2], [2, 3], [3, 1]]);

Graph 1: no cycle
Finish order: 3 1 2 0
Topological order: 0 2 1 3
Graph 2: cycle 1 -> 2 -> 3 -> 1

Graph 1's reversed finish order is a topological order, every edge pointing forwards, the subject of the topological sort lesson. Course Schedule is this program with courses for vertices.

Entry and exit order

Every vertex has two moments in a DFS: its entry, when its call starts, and its exit, when it returns. Number both with one clock and the intervals nest like brackets.

Entry order is preorder, the order for copying a tree from the top down. Exit order is postorder: a vertex finishes only after everything below it, the moment to combine its children's answers, such as subtree sizes or the deepest path below it.

How deep can the recursion go?

The pending calls are the current path, so recursion can go V calls deep.

Python stops at 1,000 frames with RecursionError; Node.js throws RangeError after roughly ten thousand, Java StackOverflowError after tens of thousands, and C++ simply crashes. When a path of more than about ten thousand vertices is possible, use the explicit stack.

Other shapes of DFS

• Search from the border. Number of Enclaves and Surrounded Regions sink everything reachable from the edge first; what is left is the answer.
• Search from the destination. Pacific Atlantic Water Flow searches uphill from each ocean once and keeps the cells both reach.
• Every path. Unmark a vertex when its call returns and DFS becomes backtracking: All Paths From Source to Target. The cost becomes exponential.

Time and space complexity

How to recognise a DFS problem

• Regions: islands, provinces, groups, "connected", "enclosed by".
• Reachability: "can every room be visited", "which cells can reach the border".
• Cycles and dependencies: "can all courses be finished", "valid tree". A directed graph wants three colours.
• Every path or arrangement: DFS with backtracking.
• Answers built from below, such as subtree sizes: postorder.

Common mistakes

• Marking after the recursive calls. Two neighbours then call each other forever.
• Reading the grid before checking bounds.
• A plain visited flag for directed cycles. A diamond is not a cycle; use three colours.
• Leaving out the parent check in an undirected graph. Every edge then looks like a cycle.
• Starting only from vertex 0. Loop over every vertex, or you miss components and cycles.

Practice in this order

1. Flood Fill: one DFS from one cell, and the trap when the new colour equals the old.
2. Number of Islands: the components loop on a grid, with sinking.
3. Max Area of Island: a DFS that returns the size it explored.
4. Number of Provinces: components of a graph given as a matrix.
5. Number of Enclaves: search from the border, then count what is left.
6. Surrounded Regions: the same border trick, then flip the rest.
7. Pacific Atlantic Water Flow: two uphill searches and their overlap.
8. Graph Valid Tree: undirected cycle detection plus connectivity.
9. Course Schedule: directed cycle detection with three colours.

The depth-first search problem list has every DFS problem in the catalogue, easiest first. With both traversals in hand, the next stage of the roadmap builds on them: topological sort, union-find and shortest paths with weights.