Depth-First Search (DFS)

Compare with BFS: BFS spreads out in waves (wide first). DFS dives down one path (deep first). Same graph, same start, different order:

Recall the stack: you push onto the top and pop from the top. Last in, first out, like a stack of plates.

In DFS, the stack holds the path you are currently on. The top is where you are now. Pushing = taking one step deeper. Popping = taking one step back. Because the most recent vertex comes off first, you always back up to the place you just came from.

Tap Next step and watch the stack grow and shrink. Before each tap, guess: go deeper or backtrack?

The three buttons are three different graphs, not three kinds of DFS. Directed starts at F: follow the arrows and see how few vertices DFS can reach. Separate pieces starts at A: DFS stops after A, B, C, because nothing connects them to the rest.

Here is the same graph searched both ways from A. The small numbers show the visit order, and the arrows show how each vertex was first reached.

Both are graph traversal algorithms: they visit every reachable vertex once. They differ in these ways:

DFS is short when written with recursion. This program builds the main example and runs DFS from A.

public class DFS {
  static char[] names = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
  static int n = names.length;
  static int[][] adj = new int[n][n];
  static boolean[] visited = new boolean[n];

  static void addEdge(int a, int b) {   // undirected
    adj[a][b] = 1;
    adj[b][a] = 1;
  }

  static void dfs(int u) {
    visited[u] = true;
    System.out.print(names[u] + " ");   // visit

    for (int v = 0; v < n; v++) {       // A to Z order
      if (adj[u][v] == 1 && !visited[v]) {
        dfs(v);                         // go deeper
      }
    }
    // loop ended: no unvisited neighbors left,
    // so this call returns (= backtrack / pop)
  }

  public static void main(String[] args) {
    addEdge(0, 1); addEdge(0, 3);   // A-B, A-D
    addEdge(1, 2); addEdge(1, 4);   // B-C, B-E
    addEdge(2, 5); addEdge(3, 4);   // C-F, D-E
    addEdge(4, 5); addEdge(4, 6);   // E-F, E-G
    addEdge(5, 6);                  // F-G
    dfs(0);   // prints: A B C F E D G
  }
}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class DFS to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

Most lines match the BFS program (see its read-aloud table). Three lines to read aloud:

 1public class Main {
 2  static char[] names = {'A', 'B', 'C', 'D', 'E', 'F'};
 3  static int n = names.length;
 4  static int[][] adj = new int[n][n];
 5  static boolean[] visited = new boolean[n];
 6
 7  static void addArrow(int from, int to) {   // directed
 8    adj[from][to] = 1;
 9  }
10
11  // DFS from u. Returns how many vertices it reaches,
12  // counting u itself.
13  static int countReach(int u) {
14    // YOUR CODE:
15    // 1. Mark u as visited.
16    // 2. Start a count at 1 (for u itself).
17    // 3. Check every v from 0 to n - 1. If v is a neighbor
18    //    of u and v is not visited yet, go deeper with
19    //    countReach(v), and add what it returns to the count.
20    // 4. Return the count.
21
22    return 0;
23  }
24
25  public static void main(String[] args) {
26    // the one-way graph from Part 4
27    addArrow(0, 1); addArrow(1, 2);   // A->B, B->C
28    addArrow(2, 0); addArrow(0, 3);   // C->A, A->D
29    addArrow(3, 4); addArrow(5, 3);   // D->E, F->D
30
31    System.out.println(countReach(0));   // expected: 5 (A B C D E)
32
33    visited = new boolean[n];            // clear for the next test
34    System.out.println(countReach(5));   // expected: 3 (F D E)
35
36    visited = new boolean[n];
37    System.out.println(countReach(4));   // expected: 1 (only E)
38
39    visited = new boolean[n];
40    System.out.println(countReach(1));   // expected: 5 (B C A D E)
41  }
42}

 1static int countReach(int u) {
 2  visited[u] = true;
 3  int count = 1;                      // u itself
 4  for (int v = 0; v < n; v++) {       // A to Z order
 5    if (adj[u][v] == 1 && !visited[v]) {
 6      count = count + countReach(v);  // go deeper
 7    }
 8  }
 9  return count;
10}

Not graded. Tap an answer to see if you got it, and read why.

Next unit: Sets in Java.