Depth-First Search (DFS)

Say you have a graph and you want to visit every vertex in it. You cannot just read it top to bottom like an array. A graph branches out in many directions. So you need a clear rule for which neighbour to walk to next. Depth-First Search gives you that rule. It says: pick one path and go as deep as you can. Then come back.

🧭 What Is DFS?

Depth-First Search (DFS) is a way to visit every vertex of a graph by going as deep as possible along one path before backing up. A vertex is just one point in the graph. An edge is the line that connects two vertices.

Think of exploring a building. You walk into one room. Then into the next room from there. Then the next one, going deeper and deeper. When a room has no new door left, you walk back to the last room that still had an unopened door. Then you go deep again from there. That walking-back part is called backtracking.

For DFS to work you need a couple of things.

• A way to go deeper. This is recursion, or you can use an explicit stack. A stack is a list where the last item you put in is the first one you take out.
• A way to remember where you have already been. This is a visited set. Without it, in a graph with cycles, you would walk in circles forever.

🌳 Deep vs Wide: DFS and BFS

People always mix up DFS with its cousin, BFS. So let us make the difference clear in one line.

• DFS goes deep. It follows one path all the way down before trying another.
• BFS goes wide. Breadth-First Search visits all the close neighbours first, then the neighbours of those, level by level.

Here is a small graph we will use for the code. The numbers are vertices.

Starting from vertex 0, DFS dives down one branch first. A valid visit order is 0, 1, 3, 5, 4, 2. See how it reached 5 deep down the first branch before ever touching 2.

🪜 Steps to Do DFS

Before we write code, let us list the plan in plain steps. We do recursive DFS from a start vertex.

1. Make a visited set (or boolean array) and mark every vertex as not visited yet.
2. Start the recursion at the start vertex.
3. When you enter a vertex, first mark it as visited. Then print it (this is the visit order).
4. Look at each neighbour of that vertex.
5. For every neighbour that is not visited yet, call DFS on that neighbour. This is the “go deeper” step.
6. When a vertex has no unvisited neighbours left, the function returns on its own. That return is the backtracking.

The graph is stored as an adjacency list. That just means: for each vertex we keep a list of the vertices it connects to.

💻 DFS in Code

Now let us turn those steps into real code. Each program builds the same graph. Then it runs recursive DFS from vertex 0. It prints the order the vertices get visited in.

#include <stdio.h>

#define V 6

// adjacency matrix: 1 means there is an edge
int graph[V][V] = {
    {0, 1, 1, 0, 0, 0}, // 0 -> 1, 2
    {0, 0, 0, 1, 1, 0}, // 1 -> 3, 4
    {0, 0, 0, 0, 1, 0}, // 2 -> 4
    {0, 0, 0, 0, 0, 1}, // 3 -> 5
    {0, 0, 0, 0, 0, 1}, // 4 -> 5
    {0, 0, 0, 0, 0, 0}  // 5 -> none
};

int visited[V] = {0};

void dfs(int vertex) {
    visited[vertex] = 1;          // mark as visited
    printf("%d ", vertex);        // print visit order
    for (int next = 0; next < V; next++) {
        // go deeper into every unvisited neighbour
        if (graph[vertex][next] == 1 && !visited[next]) {
            dfs(next);
        }
    }
}

int main() {
    printf("DFS order: ");
    dfs(0);                       // start from vertex 0
    printf("\n");
    return 0;
}

DFS order: 0 1 3 5 4 2

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

vector<vector<int>> adj = {
    {1, 2}, // 0 -> 1, 2
    {3, 4}, // 1 -> 3, 4
    {4},    // 2 -> 4
    {5},    // 3 -> 5
    {5},    // 4 -> 5
    {}      // 5 -> none
};

vector<bool> visited(6, false);

void dfs(int vertex) {
    visited[vertex] = true;       // mark as visited
    cout << vertex << " ";        // print visit order
    for (int next : adj[vertex]) {
        // go deeper into every unvisited neighbour
        if (!visited[next]) {
            dfs(next);
        }
    }
}

int main() {
    cout << "DFS order: ";
    dfs(0);                       // start from vertex 0
    cout << endl;
    return 0;
}

DFS order: 0 1 3 5 4 2

import java.util.*;

public class Dfs {
    // adjacency list for each vertex
    static List<List<Integer>> adj = Arrays.asList(
        Arrays.asList(1, 2), // 0 -> 1, 2
        Arrays.asList(3, 4), // 1 -> 3, 4
        Arrays.asList(4),    // 2 -> 4
        Arrays.asList(5),    // 3 -> 5
        Arrays.asList(5),    // 4 -> 5
        Arrays.asList()      // 5 -> none
    );

    static boolean[] visited = new boolean[6];

    static void dfs(int vertex) {
        visited[vertex] = true;       // mark as visited
        System.out.print(vertex + " ");// print visit order
        for (int next : adj.get(vertex)) {
            // go deeper into every unvisited neighbour
            if (!visited[next]) {
                dfs(next);
            }
        }
    }

    public static void main(String[] args) {
        System.out.print("DFS order: ");
        dfs(0);                       // start from vertex 0
        System.out.println();
    }
}

DFS order: 0 1 3 5 4 2

# adjacency list: each index holds the neighbours of that vertex
graph = {
    0: [1, 2],  # 0 -> 1, 2
    1: [3, 4],  # 1 -> 3, 4
    2: [4],     # 2 -> 4
    3: [5],     # 3 -> 5
    4: [5],     # 4 -> 5
    5: [],      # 5 -> none
}

visited = set()
order = []

def dfs(vertex):
    visited.add(vertex)            # mark as visited
    order.append(vertex)           # record visit order
    for neighbour in graph[vertex]:
        # go deeper into every unvisited neighbour
        if neighbour not in visited:
            dfs(neighbour)

dfs(0)                             # start from vertex 0
print("DFS order:", " ".join(map(str, order)))

DFS order: 0 1 3 5 4 2

// adjacency list: each index holds the neighbours of that vertex
const graph = {
  0: [1, 2], // 0 -> 1, 2
  1: [3, 4], // 1 -> 3, 4
  2: [4],    // 2 -> 4
  3: [5],    // 3 -> 5
  4: [5],    // 4 -> 5
  5: [],     // 5 -> none
};

const visited = new Set();
const order = [];

function dfs(vertex) {
  visited.add(vertex);             // mark as visited
  order.push(vertex);              // record visit order
  for (const neighbour of graph[vertex]) {
    // go deeper into every unvisited neighbour
    if (!visited.has(neighbour)) {
      dfs(neighbour);
    }
  }
}

dfs(0);                            // start from vertex 0
console.log("DFS order:", order.join(" "));

DFS order: 0 1 3 5 4 2

⏱️ How Fast Is DFS?

DFS is fast because it touches each vertex once and each edge once. We write the size as O(V + E), where V is the number of vertices and E is the number of edges.

Here is the cost side by side, so you can compare the two storage styles.

🔧 Where DFS Is Used

DFS is not just a school exercise. It quietly powers many real things.

• Cycle detection. While going deep, if you reach a vertex that is already on your current path, the graph has a cycle. Tools that check for circular dependencies use this.
• Topological sort. DFS gives you a valid order to do tasks when some tasks must come before others, like build steps or course prerequisites.
• Connected components. Run DFS from a vertex and it visits everything reachable from it. Whatever is left out is a separate group. This is how you find islands in a map or friend clusters in a network.
• Path and maze solving. DFS can walk a maze, trying one corridor fully before backing up to try another.

🧩 What You’ve Learned

• ✅ DFS visits a graph by going as deep as possible along one path, then backtracking.
• ✅ It needs recursion (or a stack) to go deeper and a visited set to avoid going in circles.
• ✅ DFS goes deep, while BFS goes wide, level by level.
• ✅ The steps are: mark visited, print, then recurse into each unvisited neighbour.
• ✅ DFS runs in O(V + E) time on an adjacency list, using O(V) extra space.
• ✅ It is used for cycle detection, topological sort, connected components, and maze solving.

🚀 What’s Next?

• Breadth-First Search (BFS)
• Topological Sort