Depth First Search (DFS)

Before reading, take a few minutes to explore the DFS visualizer above. Try clicking through the traversal yourself and see if you can spot the pattern. Don't worry if it doesn't make complete sense yet — we'll walk through everything together in this lesson.

The one rule of DFS

Alright, let's sit down and go through this together. There's no need to rush. We'll take it one step at a time, and by the end of this lesson, DFS will make complete sense. (And if it doesn't, send me a message and we'll figure it out together.)

Now here's the only rule you need to remember. Tattoo it on your brain if you have to.

That's what Depth First Search does.

It starts at one vertex and follows one path as deep as it can go. When it can't continue any farther, it simply returns and continues exploring from where it left off.

Keep that one simple idea in your mind as we go through the algorithm. Everything else in this lesson is just that one rule playing out, one step at a time. Ooooh... foreshadowing. 😏

Let's trace it together

Now that you know the one rule of DFS, let's see it in action. Grab your popcorn. 🍿

We can start a Depth First Search from any vertex in the graph. The traversal order may change depending on where we start, but the algorithm stays exactly the same. For this lesson, I'm simply choosing vertex 1 to keep things easy to follow.

Take your time as you read through each step. Once you see the pattern, the algorithm almost explains itself.

Step 1

Since this is the first time we've seen vertex 1, we visit it.

Vertex 1 is connected to 2, 3, and 4. Vertices directly connected by an edge are called neighbors.

DFS lets us choose any unvisited neighbor. Let's choose vertex 2 and continue exploring from there.

Step 2

We're now at vertex 2. Since this is the first time we've seen it, we visit it.

Vertex 2 is connected to 1, 5, and 6. We've already visited vertex 1, so we go one step deeper. We could choose 5 or 6 — either would work. Let's choose vertex 5.

Step 3

We're now at vertex 5. Since this is the first time we've seen it, we visit it.

Vertex 5 is connected to 2 and 7. We've already visited vertex 2, so there's only one unvisited neighbor left — vertex 7. Let's continue with vertex 7.

Step 4

We're now at vertex 7. Since this is the first time we've seen it, we visit it.

Vertex 7 is connected only to vertex 5, which we've already visited. That means there's nowhere new for us to go.

So let's return to vertex 5 and continue exploring from where we left off.

Step 5

We're back at vertex 5. We've already explored all of its neighbors, so there's nothing left to do here. Let's return to vertex 2.

Step 6

We're back at vertex 2. Earlier, we chose to visit vertex 5 first. Now let's continue exploring the remaining neighbors.

We've already visited 1 and 5. That leaves vertex 6. Let's continue with vertex 6.

Step 7

We're now at vertex 6. Since this is the first time we've seen it, we visit it.

Vertex 6 is connected to 2 and 3. We've already visited vertex 2, so there's only one unvisited neighbor left — vertex 3. Let's continue with vertex 3.

Step 8

We're now at vertex 3. Since this is the first time we've seen it, we visit it.

Vertex 3 is connected to 1 and 6. We've already visited both of them, so there's nowhere new for us to go. Let's return to vertex 6.

Step 9

We're back at vertex 6. We've already explored all of its neighbors. So let's return to vertex 2.

Step 10

We're back at vertex 2. We've now explored all of its neighbors as well. So let's return to vertex 1.

Step 11

We're back at vertex 1. Earlier, we chose vertex 2 first. Now let's continue exploring the remaining neighbors.

The next neighbor is vertex 3, but we've already visited it while exploring through vertex 6, so we'll skip it. The next unvisited neighbor is vertex 4. Let's continue with vertex 4.

Step 12

We're now at vertex 4. Since this is the first time we've seen it, we visit it.

Vertex 4 is connected to 1 and 7. We've already visited both of them, so there's nowhere new for us to go.

We've now explored every neighbor of vertex 1, which means our traversal is complete. 🎉

Final DFS traversal order

How does the computer remember where to return?

Good question. You're thinking like a programmer already. 🕵️

When we traced the graph by hand, something interesting kept happening. We'd keep exploring one path until we couldn't go any farther. Then we'd simply return to the previous vertex and continue exploring from there.

Doing that ourselves is easy. But how does the computer remember where it needs to return?

The answer is simple: a stack.

A stack follows a rule called LIFO, which stands for Last In, First Out.

Think about a stack of plates. Whenever you place another plate on the stack, it goes on top. Later, when you need a plate, you always take the plate from the top. That means the last plate you placed on the stack is the first one you take off.

DFS follows the same idea.

• Every time we're about to move to a new vertex, we first remember our current vertex by placing it on the stack.
• Then we continue exploring the new vertex.
• Eventually, when there are no new vertices left to visit, we take the vertex from the top of the stack and continue exploring from there.

That's all the stack is doing. It's simply remembering where we need to return after we've finished exploring the current path.

The full dry run

Now let's go through the same example one more time — director's cut. 🎬

This time, instead of only watching the graph, we'll also keep an eye on two things after every step.

• Visited — the vertices we've already visited.
• Stack — the vertices waiting for us to return to.

Don't worry if the stack feels a little strange at first. By the end of this walkthrough, it'll make complete sense.

Step 1

We start by visiting vertex 1. Before leaving vertex 1, we place it on the stack so we know where to return later.

Step 2

We've now arrived at vertex 2, so we visit it. From here, we could continue to vertex 5 or vertex 6. Let's choose vertex 5. Before leaving vertex 2, we place it on top of the stack.

Step 3

We've now arrived at vertex 5, so we visit it. The only unvisited neighbor left is vertex 7. Before leaving vertex 5, we place it on top of the stack.

Step 4

We've now arrived at vertex 7, so we visit it. There are no unvisited neighbors left, so we return to the previous vertex. We do that by taking the top vertex off the stack. The top of the stack is vertex 5.

Notice what just happened. We didn't have to guess where to return — the stack remembered it for us.

Step 5

We're back at vertex 5. We've already explored all of its neighbors. So once again, we return to the previous vertex. The top of the stack is vertex 2.

Step 6

We're back at vertex 2. The next unvisited neighbor is vertex 6. Before leaving vertex 2, we place it on the stack again.

Step 7

We've now arrived at vertex 6, so we visit it. The only unvisited neighbor left is vertex 3. Before leaving vertex 6, we place it on the stack.

Step 8

We've now arrived at vertex 3, so we visit it. There are no unvisited neighbors left. So we return to vertex 6 by taking it from the top of the stack.

Step 9

We're back at vertex 6. We've already explored all of its neighbors. So we return to vertex 2.

Step 10

We're back at vertex 2. We've now explored all of its neighbors. So we return to vertex 1.

Step 11

We're back at vertex 1. We've already visited vertex 3, so we'll skip it. The next unvisited neighbor is vertex 4.

Step 12

We've now arrived at vertex 4, so we visit it. There are no unvisited neighbors left. The stack is now empty, which means there's nowhere left to return.

Our Depth First Search is complete. 🎉

Final DFS traversal order

Now let's build it in code

Now that we've traced DFS by hand, it's time to teach the computer to do the exact same thing.

Don't worry — we're not learning a new algorithm anymore. We're simply turning the steps we already followed into C code. We'll build the program one piece at a time.

Step 1 — Representing the graph

Just like in our BFS program, we'll represent the graph using an adjacency matrix. Each row and column represents a vertex. A value of 1 means an edge exists. A value of 0 means there isn't one.

int A[8][8] = {
    {0,0,0,0,0,0,0,0},
    {0,0,1,1,1,0,0,0},
    {0,1,0,0,0,1,1,0},
    {0,1,0,0,0,0,1,0},
    {0,1,0,0,0,0,0,1},
    {0,0,1,0,0,0,0,1},
    {0,0,1,1,0,0,0,0},
    {0,0,0,0,1,1,0,0}
};

We're using an 8 × 8 matrix even though our graph only has 7 vertices. That's because we're ignoring index 0 and using the vertex numbers directly as array indices. Poor index 0 is unemployed once again. 😔

Step 2 — Keeping track of visited vertices

We also need a way to remember which vertices we've already visited. Otherwise, we'd keep visiting the same vertices again and again.

int visited[8] = {0};

Initially, every value is 0. A value of 0 means the vertex hasn't been visited yet. As soon as we visit a vertex, we'll change its value to 1.

Step 3 — Writing the DFS function

Now it's time to write the function that performs the Depth First Search.

void DFS(int u)
{

The parameter u represents the current vertex we're exploring. When we call DFS(1), the function starts from vertex 1. When it later calls DFS(5), it starts from vertex 5. In other words, u simply tells the function which vertex it's currently working on.

The first thing we do is check whether we've already visited the current vertex.

if (visited[u] == 0)
{

If the answer is no, we visit it — print it and mark it as visited.

    printf("%d ", u);
    visited[u] = 1;

Once we've visited the current vertex, we need to look at every possible connection from it.

    for (int v = 1; v <= n; v++)
    {

For every column in the current row, we check whether an edge exists and whether that neighbor hasn't been visited yet.

        if (A[u][v] == 1 && visited[v] == 0)
        {

Only if both answers are yes do we continue. And continuing simply means calling the same function again for the new vertex.

            DFS(v);
        }
    }
}

At first, DFS(v) might look a little strange. The function is calling... itself? This is called recursion, and we'll understand exactly how it handles returning in just a moment.

Wait... how did the program return?

When the program finished exploring vertex 7, we never wrote code saying "go back to vertex 5." Yet somehow... it returned there anyway.

The answer is recursion.

Whenever a recursive function calls itself, the computer automatically remembers where it needs to continue after that function finishes. So when DFS(7) is done, the computer already knows to continue from DFS(5). When DFS(5) finishes, it continues from DFS(2). And when DFS(2) finishes, it continues from DFS(1).

We never had to write code telling the program where to return. Recursion quietly takes care of that for us. Pretty cool, right?

Putting everything together

We've now written every piece of our DFS function. Let's combine them into one complete function.

void DFS(int u)
{
    int v;

    if (visited[u] == 0)
    {
        printf("%d ", u);
        visited[u] = 1;

        for (v = 1; v <= n; v++)
        {
            if (A[u][v] == 1 && visited[v] == 0)
            {
                DFS(v);
            }
        }
    }
}

Take a moment to compare this function with the dry run we performed earlier. The code isn't doing anything magical — it's simply repeating the exact same steps we followed by hand.

1. Visit the current vertex.
2. Mark it as visited.
3. Look at all of its neighbors.
4. If an unvisited neighbor is found, explore it.
5. Repeat until there are no new vertices left to visit.

The complete program

Now let's put everything together into one complete program you can compile and run.

#include <stdio.h>

int n = 7;

int A[8][8] = {
    {0,0,0,0,0,0,0,0},
    {0,0,1,1,1,0,0,0},
    {0,1,0,0,0,1,1,0},
    {0,1,0,0,0,0,1,0},
    {0,1,0,0,0,0,0,1},
    {0,0,1,0,0,0,0,1},
    {0,0,1,1,0,0,0,0},
    {0,0,0,0,1,1,0,0}
};

int visited[8] = {0};

void DFS(int u)
{
    int v;

    if (visited[u] == 0)
    {
        printf("%d ", u);
        visited[u] = 1;

        for (v = 1; v <= n; v++)
        {
            if (A[u][v] == 1 && visited[v] == 0)
            {
                DFS(v);
            }
        }
    }
}

int main()
{
    DFS(1);

    return 0;
}

Let's watch the program run

Rather than only looking at the final output, let's see what the program is doing at each step.

Visit 1 (start)

Exploring 2 from 1

Visit 2

Exploring 5 from 2

Visit 5

Exploring 7 from 5

Visit 7

No unvisited neighbors from 7
Returning to 5

No unvisited neighbors from 5
Returning to 2

Exploring 6 from 2

Visit 6

Exploring 3 from 6

Visit 3

No unvisited neighbors from 3
Returning to 6

No unvisited neighbors from 6
Returning to 2

No unvisited neighbors from 2
Returning to 1

Vertex 3 is already visited
Skipping it

Exploring 4 from 1

Visit 4

No unvisited neighbors from 4
Returning to 1

DFS complete.

Final DFS order:
1 2 5 7 6 3 4

Notice how this narration matches the walkthrough we did earlier. The program keeps exploring deeper until it can't go any farther. Then it returns to the previous vertex and continues exploring from where it left off.

Time complexity

Now that we understand how DFS works, let's figure out how much work it actually does. We'll analyze it using the adjacency matrix representation we've been using throughout this lesson.

Visiting the vertices

The first thing DFS does is visit the vertices. Notice that each vertex is visited only once — as soon as we visit a vertex, we mark it as visited and skip it if we reach it again. Since there are n vertices, visiting them takes O(n) time.

Checking the edges

While exploring a vertex, DFS scans the entire row of the adjacency matrix.

for (v = 1; v <= n; v++)

Each row contains n columns, so checking one row takes O(n) time. Since DFS eventually explores all n vertices, it ends up scanning n rows. That means the total work is n × n = n². The overall time complexity is:

when the graph is represented using an adjacency matrix.

What if we used an adjacency list?

With an adjacency list, we don't scan an entire row. Instead, we only look at the vertices that are actually connected. That means every vertex is visited once, and every edge is examined once. So the time complexity becomes:

where V is the number of vertices and E is the number of edges. You'll see this time complexity in most textbooks because DFS is usually implemented using an adjacency list.

The big picture

Let's quickly recap what we learned.

One last thing...

Throughout this lesson, we kept saying things like "return to vertex 5" or "go back to vertex 2."

There's actually a name for that.

It's called backtracking. Backtracking simply means returning to a previous point after you've finished exploring the current path.

The nice part is... you've already been doing it this whole time. We just didn't give it a name until now. Sometimes it's easier to experience an idea first and learn the terminology later. And that's exactly what you did.

Congratulations! 🎉 You now know how Depth First Search works, how to implement it in code, and why it behaves the way it does.

See you in the next lesson. 👋