Lesson 33 of 50 14 minAdvanced

Depth-first search

Explore as deep as possible before backing up, recursively or with a stack, and use DFS to find connected components, detect cycles and reason about dependencies.

Depth-first search (DFS) explores like someone walking a maze with one hand on the wall: keep going forward to a new place as long as you can; when you hit a dead end, back up to the last junction with an unexplored way and continue from there. It visits the same vertices as BFS, in a very different order, and the order itself turns out to be useful.

Recursive DFS

The call stack does the backing up for you: when the recursive call for a neighbour returns, you are back at the previous vertex and continue with its next neighbour.

Dfs.cs

1var adj = new Dictionary<char, char[]>2{3    ['A'] = new[] { 'B', 'D' },4    ['B'] = new[] { 'A', 'C', 'E' },5    ['C'] = new[] { 'B', 'E', 'F' },6    ['D'] = new[] { 'A', 'E', 'G' },7    ['E'] = new[] { 'B', 'C', 'D', 'F', 'G' },8    ['F'] = new[] { 'C', 'E', 'G' },9    ['G'] = new[] { 'D', 'E', 'F' }10};11 12var visited = new HashSet<char>();13var order = new List<char>();14Visit('A');15Console.WriteLine(string.Join(" ", order));16 17void Visit(char u)18{19    visited.Add(u);20    order.Add(u);21    foreach (char v in adj[u])22        if (!visited.Contains(v))23            Visit(v);                    // go deeper; when it returns, we are back at u24}

Output

A B C E D G F

Compare with BFS on the same graph (A B D C E G F): DFS dives down one long path A → B → C → E → D → G → F before it ever looks at A’s second neighbour. Time is the same O(V + E); memory is O(depth) for the recursion.

Iterative DFS with a stack

On a very large graph the recursion can be thousands of calls deep and overflow the stack. Swap the queue in BFS for a Stack<T> and you get a depth-first order without recursion:

DfsIterative.cs

1var adj = new Dictionary<char, char[]>2{3    ['A'] = new[] { 'B', 'D' },4    ['B'] = new[] { 'A', 'C', 'E' },5    ['C'] = new[] { 'B', 'E', 'F' },6    ['D'] = new[] { 'A', 'E', 'G' },7    ['E'] = new[] { 'B', 'C', 'D', 'F', 'G' },8    ['F'] = new[] { 'C', 'E', 'G' },9    ['G'] = new[] { 'D', 'E', 'F' }10};11 12var visited = new HashSet<char>();13var order = new List<char>();14var stack = new Stack<char>();15stack.Push('A');16while (stack.Count > 0)17{18    char u = stack.Pop();19    if (!visited.Add(u)) continue;              // already visited via another route20    order.Add(u);21    foreach (char v in adj[u].Reverse())         // reversed, so the first neighbour is popped first22        if (!visited.Contains(v)) stack.Push(v);23}24Console.WriteLine(string.Join(" ", order));

Output

A B C E D G F

Connected components

Is the site network in one piece, or are some places cut off? Start a DFS from every vertex that is not visited yet. Each start discovers one whole connected component. The number of starts is the number of components.

Components.cs

1int n = 8;2int[][] links = { new[] { 0, 1 }, new[] { 1, 2 }, new[] { 3, 4 }, new[] { 5, 6 }, new[] { 6, 7 }, new[] { 5, 7 } };3 4var adj = new List<int>[n];5for (int i = 0; i < n; i++) adj[i] = new List<int>();6foreach (var e in links) { adj[e[0]].Add(e[1]); adj[e[1]].Add(e[0]); }7 8var group = new int[n];9Array.Fill(group, -1);10int groups = 0;11for (int s = 0; s < n; s++)12{13    if (group[s] != -1) continue;14    Mark(s, groups++);                       // a new component starts here15}16Console.WriteLine($"{groups} components: {string.Join(" ", group)}");17 18void Mark(int u, int id)19{20    group[u] = id;21    foreach (int v in adj[u])22        if (group[v] == -1) Mark(v, id);23}

Output

3 components: 0 0 0 1 1 2 2 2

Finding cycles in dependencies

In a directed graph of dependencies, a cycle means an impossible plan: A needs B, B needs C, C needs A. DFS finds it by remembering which vertices are on the current path. If DFS reaches a vertex that is still on the current path, it has walked in a circle. (Visited-but-finished vertices are fine: that is just two routes to the same task.)

CycleCheck.cs

1var deps = new Dictionary<string, string[]>2{3    ["Excavate"] = new[] { "Footings" },4    ["Footings"] = new[] { "Columns" },5    ["Columns"] = new[] { "Beams" },6    ["Beams"] = new[] { "Deck" },7    ["Deck"] = new[] { "Roof" },8    ["Roof"] = Array.Empty<string>()9};10Console.WriteLine(HasCycle(deps));11 12deps["Roof"] = new[] { "Excavate" };            // a wrong dependency13Console.WriteLine(HasCycle(deps));14 15static bool HasCycle(Dictionary<string, string[]> g)16{17    var state = new Dictionary<string, int>();  // missing = new, 1 = on the current path, 2 = finished18    foreach (var node in g.Keys)19        if (Visit(node)) return true;20    return false;21 22    bool Visit(string u)23    {24        int s = state.GetValueOrDefault(u);25        if (s == 1) return true;                // back on the current path: a cycle26        if (s == 2) return false;               // already fully explored27        state[u] = 1;28        foreach (var v in g[u])29            if (Visit(v)) return true;30        state[u] = 2;                           // leaving u: no longer on the path31        return false;32    }33}

Output

False
True

BFS or DFS?

Need	Use
Shortest path by number of steps	BFS
Nearest something	BFS
Just “can I reach it?” / visit everything	Either (DFS is often simpler to write)
Connected components, flood fill	Either
Cycle detection, topological order, dependency checks	DFS
Explore all solutions of a puzzle (backtracking)	DFS

Quick check

In the CycleCheck code, why is reaching a vertex with state 2 (finished) not a cycle?

Quick check

What replaces the queue of BFS in an iterative DFS?

Practice

Write CountComponents(int n, int[][] links) using DFS with an explicit Stack<int> (no recursion). For n = 7 and links (0,1), (1,2), (3,4), (5,5) the answer is 4: {0,1,2}, {3,4}, {5} and {6}.

Show a hint

Build the adjacency list. For each unvisited vertex, add 1 to the count, push it, and pop/push until the stack is empty, marking vertices as visited.

Show the solution

Solution.cs

1Console.WriteLine(CountComponents(7, new[] { new[] { 0, 1 }, new[] { 1, 2 }, new[] { 3, 4 }, new[] { 5, 5 } }));2 3static int CountComponents(int n, int[][] links)4{5    var adj = new List<int>[n];6    for (int i = 0; i < n; i++) adj[i] = new List<int>();7    foreach (var e in links) { adj[e[0]].Add(e[1]); adj[e[1]].Add(e[0]); }8 9    var seen = new bool[n];10    int count = 0;11    for (int s = 0; s < n; s++)12    {13        if (seen[s]) continue;14        count++;15        var stack = new Stack<int>();16        stack.Push(s);17        seen[s] = true;18        while (stack.Count > 0)19        {20            int u = stack.Pop();21            foreach (int v in adj[u])22                if (!seen[v]) { seen[v] = true; stack.Push(v); }23        }24    }25    return count;26}

Output

Remember

DFS goes as deep as possible, then backs up; recursion or an explicit stack, O(V + E).
One DFS per unvisited vertex finds the connected components.
In directed graphs, reaching a vertex still on the current path means a cycle.
Use BFS for shortest steps; DFS for cycles, ordering, dependencies and backtracking.

Foundations

Linear data structures

Searching and sorting

Hashing and problem-solving techniques

Trees

Graphs

Algorithm design

Master level

Depth-first search