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.

• Visit vertex 1.
• Vertex 1's neighbors: 2, 3, 4. Choose vertex 2.
• Move to vertex 2.

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.

• Visit vertex 2.
• Vertex 2's neighbors: 1 (visited), 5, 6. Choose vertex 5.
• Move to 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 only to vertex 2, which we've already visited. That means there's nowhere new for us to go.

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

• Visit vertex 5.
• Only neighbor: vertex 2 (already visited). Nowhere new to go.
• Return to vertex 2.

Step 4

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.

• Back at vertex 2. Vertices 1 and 5 already visited.
• Only unvisited neighbor left: vertex 6. Choose vertex 6.
• Move to vertex 6.

Step 5

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.

• Visit vertex 6.
• Vertex 6's neighbors: 2 (visited), 3. Choose vertex 3.
• Move to vertex 3.

Step 6

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.

• Visit vertex 3.
• Vertex 3's neighbors: 1 (visited), 6 (visited). Nowhere new to go.
• Return to vertex 6.

Step 7

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

• Back at vertex 6. All neighbors already visited.
• Return to vertex 2.

Step 8

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

• Back at vertex 2. All neighbors already visited.
• Return to vertex 1.

Step 9

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.

• Back at vertex 1. Vertex 2 visited. Vertex 3 already visited (reached through vertex 6). Skip it.
• Only unvisited neighbor left: vertex 4. Choose vertex 4.
• Move to vertex 4.

Step 10

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 vertex 1, so there's only one unvisited neighbor left — vertex 7. Let's continue with vertex 7.

• Visit vertex 4.
• Vertex 4's neighbors: 1 (visited), 7. Choose vertex 7.
• Move to vertex 7.

Step 11

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 4, which we've already visited. That means there's nowhere new for us to go.

So let's return to vertex 4.

• Visit vertex 7.
• Only neighbor: vertex 4 (already visited). Nowhere new to go.
• Return to vertex 4.

Step 12

We're back at vertex 4. We've already explored all of its neighbors, so let's return to vertex 1 one last time.

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

• Back at vertex 4. All neighbors already visited.
• Return to vertex 1.
• All of vertex 1's neighbors visited. Traversal 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. 🎬

Before we start, let's keep the stack rule super simple in our heads:

• Push = we place a vertex on top of the stack (when we're about to go explore deeper from it).
• Pop = we remove the vertex from the top of the stack (when we need to return to it).

That's it. Every single step below is just one of these two actions happening, over and over. We'll track two things after every step:

• Visited — the vertices we've already visited.
• Stack — the vertices waiting for us to return to (top listed first).

Step 1

We start at 1 and visit it. From 1's neighbors we can choose any, let's choose 2. Since DFS only goes deeper, we won't visit 1's other neighbors (3, 4) right now, but we'll need to come back to 1 later for those. So we push 1 onto the stack first. Then we move to 2.

So our step will be:

• Visit 1
• Choose 2 to go deeper into
• Push 1 onto the stack
• Visit 2

Visited: 1, 2
Stack (top to bottom): 1

Step 2

Now we are at 2. 2's neighbors are 1, 5, and 6. 1 is already visited, so we can choose between 5 and 6, let's choose 5. Since 2 still has 6 left to explore later, we push 2 onto the stack first, then visit 5.

So our step will be:

• Choose 5 to go deeper into
• Push 2 onto the stack
• Visit 5

Visited: 1, 2, 5
Stack (top to bottom): 2, 1

Step 3

Now we are at 5. 5's only neighbor is 2, and that's already visited, so there's nowhere new to go from here. Whenever there's nowhere to go, we look at the stack and pop it, whatever is on top comes off, and we move there. Right now 2 is on top of the stack, so 2 comes off and we move to 2.

So our step will be:

• No unvisited neighbors left
• Look at stack and pop, 2 comes off
• Move to 2

Visited: 1, 2, 5
Stack (top to bottom): 1

Step 4

We're back at 2. Earlier we explored 5 first, now let's check what's left. 2's neighbors are 1, 5, and 6. 1 and 5 are already visited, so only 6 remains. We push 2 onto the stack again, then move to 6.

So our step will be:

• Choose 6 to visit
• Push 2 onto the stack
• Visit 6

Visited: 1, 2, 5, 6
Stack (top to bottom): 2, 1

Step 5

We are at 6. 6's neighbors are 2 and 3. 2 is already visited, so only 3 remains. We push 6 onto the stack, then move to 3 and visit it.

So our step will be:

• Choose 3 to go deeper into
• Push 6 onto the stack
• Visit 3

Visited: 1, 2, 5, 6, 3
Stack (top to bottom): 6, 2, 1

Step 6

We are at 3. 3's neighbors are 1 and 6, both already visited, so there's nowhere new to go. So whenever there's nowhere to go, we look at the stack and pop it. Right now 6 is on top, so 6 comes off and we move to 6.

So our step will be:

• No unvisited neighbors left
• Look at stack and pop, 6 comes off
• Move to 6

Visited: 1, 2, 5, 6, 3
Stack (top to bottom): 2, 1

Step 7

We're back at 6. We already checked both its neighbors, 2 and 3, and both are visited, so there's nothing left to explore here. Again, nowhere to go, so we look at the stack and pop it. 2 is on top, so 2 comes off and we move to 2.

So our step will be:

• Check 6's neighbors, none unvisited
• Look at stack and pop, 2 comes off
• Move to 2

Stack (top to bottom): 1

Step 8

We're back at 2. We already checked all its neighbors, 1, 5, and 6, and all are visited, so there's nothing left here either. Nowhere to go, so we look at the stack and pop it. 1 is on top, so 1 comes off and we move to 1.

So our step will be:

• Check 2's neighbors, none unvisited
• Look at stack and pop, 1 comes off
• Move to 1

Stack: empty

Step 9

We're back at 1. Earlier we chose 2 first, now let's check what's left. 1's neighbors are 2, 3, and 4. 2 is visited, and 3 is also already visited since we reached it through 6. So the only unvisited neighbor left is 4. We push 1 onto the stack, then move to 4.

So our step will be:

• Check 1's remaining neighbors, skip 3, choose 4
• Push 1 onto the stack
• Visit 4

Stack (top to bottom): 1

Step 10

We are at 4. 4's neighbors are 1 and 7. 1 is already visited, so only 7 remains. We push 4 onto the stack, then move to 7 and visit it.

So our step will be:

• Choose 7 to go deeper into
• Push 4 onto the stack
• Visit 7

Visited: 1, 2, 5, 6, 3, 4
Stack (top to bottom): 4, 1

Step 11

We are at 7. 7's only neighbor is 4, already visited, so there's nowhere new to go. Nowhere to go, so we look at the stack and pop it. 4 is on top, so 4 comes off and we move to 4.

So our step will be:

• No unvisited neighbors left
• Look at stack and pop, 4 comes off
• Move to 4

Visited: 1, 2, 5, 6, 3, 4, 7
Stack (top to bottom): 1

Step 12

We're back at 4. We already checked both its neighbors, 1 and 7, and both are visited, so nothing left here. Nowhere to go, so we look at the stack and pop it. 1 is on top, so 1 comes off and we move to 1.

So our step will be:

• Check 4's neighbors, none unvisited
• Look at stack and pop, 1 comes off
• Move to 1

Stack: empty

We're back at 1 one last time. All of its neighbors, 2, 3, and 4, are visited. There's nowhere to go, so we look at the stack, but the stack is empty, so there's nowhere left to pop from. Our Depth First Search is complete.

Final DFS Traversal

Notice how every single move in this whole walkthrough was just one of two things: push (about to explore deeper) or pop (nowhere left to go, so step back). That's genuinely the entire idea behind how DFS remembers its way back — nothing more complicated than that.

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

We'll represent the graph using an adjacency matrix. Each row and column represents a vertex. A value of 1 means an edge exists between the two vertices; a value of 0 means there isn't one.

Based on our graph — 1 connects to 2, 3, 4 · 2 connects to 1, 5, 6 · 3 connects to 1, 6 · 4 connects to 1, 7 · 5 connects to 2 · 6 connects to 2, 3 · 7 connects to 4 — the matrix looks like this:

int A[8][8] = {
    {0,0,0,0,0,0,0,0},
    {0,0,1,1,1,0,0,0},   // 1 -> 2, 3, 4
    {0,1,0,0,0,1,1,0},   // 2 -> 1, 5, 6
    {0,1,0,0,0,0,1,0},   // 3 -> 1, 6
    {0,1,0,0,0,0,0,1},   // 4 -> 1, 7
    {0,0,1,0,0,0,0,0},   // 5 -> 2
    {0,0,1,1,0,0,0,0},   // 6 -> 2, 3
    {0,0,0,0,1,0,0,0}    // 7 -> 4
};

We're using an 8 × 8 matrix even though our graph only has 7 vertices, 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 need a way to remember which vertices we've already visited, otherwise we'd keep visiting the same ones again and again.

int visited[8] = {0};

Every value starts at 0 (not visited). As soon as we visit a vertex, we 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 — and this time, we'll also make it print the same kind of narration we used in our walkthrough ("Visit", "Exploring", "Returning").

void DFS(int u, int parent)
{

u is the vertex we're currently exploring. parent is the vertex we came from — the one we should return to once we're done here. When we start at vertex 1, there's no parent, so we'll pass in 0 to mean "no parent."

Visit the current vertex

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

Every time DFS is called on a new vertex, it immediately visits it and marks it as visited. Since we only ever call DFS(u, parent) on unvisited vertices (we check before calling), we don't even need the if (visited[u] == 0) check inside anymore — it's guaranteed.

Looking for the next vertex

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

This loop scans the current vertex's row in the matrix, checking every other vertex v. We only continue if two things are true: there's an edge (A[u][v] == 1), and that vertex hasn't been visited yet (visited[v] == 0).

Going deeper

        printf("Exploring %d from %d\n", v, u);
        DFS(v, u);
    }
}

If we find an unvisited neighbor, we print that we're exploring it, then call DFS on it — passing in u as its parent, so it knows who to return to when it's done.

Returning

printf("No unvisited neighbors from %d\n", u);

if (parent != 0)
    printf("Returning to %d\n\n", parent);
else
    printf("DFS complete.\n");

Once the loop finishes, it means every neighbor of u has already been visited — there's nowhere new to go from here. So we print that, and then return to whoever called us: the parent. If there's no parent (we're back at the very start, vertex 1), the whole traversal is complete.

Putting it all together

void DFS(int u, int parent)
{
    int v;

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

    for (v = 1; v <= n; v++)
    {
        if (A[u][v] == 1 && visited[v] == 0)
        {
            printf("Exploring %d from %d\n", v, u);
            DFS(v, u);
        }
    }

    printf("No unvisited neighbors from %d\n", u);

    if (parent != 0)
        printf("Returning to %d\n\n", parent);
    else
        printf("DFS complete.\n");
}

Notice this function isn't doing anything new conceptually — it's the exact same rule we've followed since the very beginning: visit, explore neighbors, and return when there's nowhere left to go. We've just taught the computer to say out loud what it's doing, by passing along who called it.

Wait — Where's the Stack in the Code?

If you look back at our DFS() function, you might notice something: there's no stack[] array anywhere. We never wrote a push() or pop(). So where did the stack go?

Here's the trick: recursion is a stack. We just don't have to write it ourselves — the computer keeps one for us automatically.

Every time a function calls itself, the computer pauses the current call exactly where it is, remembers that spot, and jumps into the new call. That pausing-and-remembering is the push. When the new call finishes and returns, control goes right back to the exact place it paused — that's the pop.

So this single line:

DFS(v, u);

is secretly doing the push for us. Calling DFS(5, 2) from inside DFS(2, 1) means: "pause DFS(2, 1) right here, and go run DFS(5, 2) now." And when DFS(5, 2) finishes and hits its closing }, that's the pop — we land right back inside DFS(2, 1), at the exact spot we left off.

Here's how our hand-traced stack maps onto the actual code:

So we never coded a stack because we didn't need to — the chain of function calls forms one on its own. The push/pop dry run we did by hand earlier was really just us pretending to be the computer, doing manually what recursion gives us for free.

This is also why the parent argument matters so much. It's not just there for the printf messages — it's literally recording who to "return to," the same job the stack was doing. Once a vertex runs out of unvisited neighbors, parent tells it exactly where to pop back to.

The complete program

#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,0},
    {0,0,1,1,0,0,0,0},
    {0,0,0,0,1,0,0,0}
};

int visited[8] = {0};

void DFS(int u, int parent)
{
    int v;

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

    for (v = 1; v <= n; v++)
    {
        if (A[u][v] == 1 && visited[v] == 0)
        {
            printf("Exploring %d from %d\n", v, u);
            DFS(v, u);
        }
    }

    printf("No unvisited neighbors from %d\n", u);

    if (parent != 0)
        printf("Returning to %d\n\n", parent);
    else
        printf("DFS complete.\n");
}

int main()
{
    DFS(1, 0);   // start at vertex 1, no parent
    return 0;
}

Let's watch the program run

This is the real, compiled output of the program above — nothing added by hand:

Visit 1
Exploring 2 from 1
Visit 2
Exploring 5 from 2
Visit 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

Exploring 4 from 1
Visit 4
Exploring 7 from 4
Visit 7
No unvisited neighbors from 7
Returning to 4

No unvisited neighbors from 4
Returning to 1

No unvisited neighbors from 1
DFS complete.

This lines up exactly with the graph, the stack dry-run, and everything we traced by hand. Every "Returning to X" here is really the parent value doing what the stack was doing conceptually — remembering the path back.

Final DFS order (from the "Visit" lines):

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. 👋