Breadth First Search (BFS)

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, BFS will make complete sense. (And if it doesn't, send me a message and I'll make sure you understand it.)

The one rule of BFS

Before we begin, there's one small term you should know.

A neighbor is simply a vertex that is directly connected to another vertex. Basically, graph besties.

For example, the neighbors of 1 are 2, 3, and 4 because they're connected directly to 1. Similarly, the neighbors of 2 are 1, 5, and 6.

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

That's what Breadth First Search does. It starts at one vertex, visits every vertex directly connected to it, and only then continues exploring the graph. Very polite algorithm — finishes saying hi to everyone in the room before wandering off to the next one.

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

Let's trace it together

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

We'll use the graph below and start from vertex 1. Take your time as you read through each step. Once you see the pattern, the algorithm almost explains itself.

Step 1

We start at vertex 1. The main character has entered the chat.

It is connected to 2, 3, and 4. None of them have been visited yet, so we visit each of them.

We've now finished exploring vertex 1, so it's time to move on.

Step 2

Next, we explore vertex 2.

It is connected to 1, 5, and 6. We've already visited 1, so we only visit 5 and 6. (Sorry 1, we've already met — no need to reintroduce yourself.)

Step 3

Now we explore vertex 3.

It is connected to 1 and 6, but both have already been visited. That means there's nothing new to do here.

And that's completely normal. Not every vertex leads to a new discovery. Sometimes you show up to the party and everyone's already there. Awkward, but fine!

This is also why we keep track of visited vertices. Without doing that, we'd keep visiting the same vertices again and again whenever we found another path to them — like that one relative who tells you the same story every Thanksgiving.

Step 4

Next, we explore vertex 4.

It is connected to 1 and 7. Since 1 has already been visited, we only visit 7. Fresh face! Welcome, 7.

Step 5

Finally, we explore vertices 5, 6, and 7.

Each of them is connected only to vertices we've already visited, so there are no new vertices left to discover. Everyone's been met. The graph has run out of strangers.

At this point, BFS is complete. 🎊

Final visit order

And that's it. You just traced an entire Breadth First Search by hand. Look at you go!

Hopefully, it doesn't feel nearly as intimidating now.

How does the computer remember what's next?

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

BFS tells us to finish the current level before moving on to the next one. But how does the computer remember which vertex should be explored next?

The answer is simple.

A queue.

A queue follows a rule called FIFO, which stands for First In, First Out. The first item to enter the queue is also the first one to leave it.

Think about standing in line at a grocery store. The person who joins the line first gets served first. Nobody skips ahead. (And if they try — chaos. Don't be that person.)

BFS follows that same idea using two simple rules.

• Whenever we discover a new vertex, we add it to the back of the queue.
• We always explore the vertex at the front of the queue.

That's it. Those two rules are what keep BFS moving through the graph one level at a time.

The full dry run

Now let's go through the same example again — director's cut. This time, instead of only looking at the graph, we'll also keep an eye on two things after every step.

• Visited shows every vertex we've already discovered.
• Queue shows which vertices are waiting to be explored.

Once you see these two changing together, BFS becomes much easier to understand.

Step 1

We start by visiting vertex 1 and adding it to the queue.

Step 2

We remove 1 from the front of the queue and explore it.

It is connected to 2, 3, and 4. Since none of them have been visited yet, we visit each one and add them to the back of the queue.

Step 3

Next, we remove 2 from the front of the queue.

It is connected to 1, 5, and 6. We skip 1 because it's already visited. Then we visit 5 and 6, adding both to the back of the queue.

Step 4

Now we remove 3 from the front of the queue.

It is connected to 1 and 6, but both have already been visited, so nothing changes. Vertex 3 just clocks in and clocks out. 😴

Step 5

Next, we remove 4 from the front of the queue.

It is connected to 1 and 7. Since 1 has already been visited, we only visit 7 and add it to the back of the queue.

Step 6

Finally, we remove 5, 6, and 7 one by one.

Each of them is connected only to vertices we've already visited, so no new vertices are added to the queue. The graph is officially out of surprises.

The queue is now empty, which means there's nothing left to explore.

BFS is complete. 🏁

Take a moment to notice the pattern. Every iteration does the same thing.

1. Remove a vertex from the front of the queue.
2. Explore its neighbors.
3. Visit any new neighbors and add them to the back of the queue.

That simple cycle repeats until the queue becomes empty. And that's Breadth First Search. Three steps on a loop — that's the whole trick.

Now let's build it in code

Here's the good news.

You already know how Breadth First Search works. We aren't learning a new algorithm anymore. We're simply teaching the computer to follow the exact steps you just followed by hand. Basically, we're writing a very obedient robot version of you.

If you think back to our dry run, we only needed three things.

• A way to remember which vertices we've already visited.
• A queue to remember which vertex to explore next.
• A way to find all the neighbors of the current vertex.

Let's build each of those, one step at a time.

Piece 1. Representing the graph

We'll store our graph using an adjacency matrix.

It's simply a grid where each row and column represents a vertex. If two vertices are connected, we store 1. Otherwise, we store 0. Very binary, very no-nonsense.

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}
};

You might notice that the matrix is 8 × 8, even though our graph only has 7 vertices.

That's because we're leaving index 0 unused. This lets the vertex numbers match the array indices, so vertex 1 is stored at index 1, vertex 2 at index 2, and so on. It keeps the code a little cleaner. (Index 0 just sits there unemployed the whole time. Living its best life.)

For example,

• A[1][2] = 1 means vertices 1 and 2 are connected.
• A[3][5] = 0 means vertices 3 and 5 are not connected.

That's all an adjacency matrix really is. A table of yes-or-no answers.

Piece 2. Keeping track of visited vertices

One of the most important rules of BFS is that each vertex should be visited only once. No do-overs!

We'll use a simple array to remember that.

int visited[8] = {0};

Every value starts as 0, meaning the vertex hasn't been visited yet.

The first time we visit a vertex, we change its value to 1.

From that point on, if we ever reach the same vertex again through another path, we'll simply skip it. It's basically the algorithm's version of "yeah, we've met."

Piece 3. The queue

Finally, we need a queue.

You already know why.

Whenever we discover a new vertex, we add it to the back of the queue. Whenever we're ready to explore another vertex, we remove one from the front.

That's exactly the process we followed during the dry run.

int q[100];
int front = 0, rear = 0;

int isEmpty(int q[])
{
    return front == rear;
}

void enqueue(int q[], int val)
{
    q[rear++] = val;
}

int dequeue(int q[])
{
    return q[front++];
}

And since we want to actually see the queue as it changes shape, we add one small helper:

void printQueue()
{
    printf("   Queue now: [ ");
    for (int i = front; i < rear; i++)
        printf("%d ", q[i]);
    printf("]\n");
}

Putting everything together

Let's translate our dry run into code.

The first thing we do is visit the starting vertex.

printf("Visit %d (start)\n", start);

Since we've now visited it, we mark it as visited.

visited[start] = 1;

Even though we've visited it, we still haven't explored its neighbors. So we place it in the queue.

enqueue(q, start);
printQueue();

Now comes the heart of the algorithm. 💓

As long as the queue isn't empty, there are still vertices waiting to be explored.

while (!isEmpty(q))
{

We remove the vertex at the front of the queue, and announce it.

    int u = dequeue(q);
    printf("Dequeue %d, exploring its neighbors:\n", u);

Next, we look through every possible vertex to see whether it's connected to u.

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

Whenever we find a connected vertex that hasn't been visited yet, we do the same three things we've been doing since the beginning of this lesson.

1. Visit it.
2. Mark it as visited.
3. Add it to the queue.

        if (A[u][v] == 1 && visited[v] == 0)
        {
            printf("Visit %d (neighbor of %d)\n", v, u);
            visited[v] = 1;
            enqueue(q, v);
            printQueue();
        }
    }
}

Notice how those same three steps keep appearing again and again. Like a catchy chorus you can't get out of your head.

That's really all BFS is.

The complete function

Putting everything together gives us the complete BFS implementation. Ta-da! 🪄

void BFS(int start)
{
    printf("Visit %d (start)\n", start);
    visited[start] = 1;
    enqueue(q, start);
    printQueue();

    while (!isEmpty(q))
    {
        int u = dequeue(q);
        printf("Dequeue %d, exploring its neighbors:\n", u);

        for (int v = 1; v <= n; v++)
        {
            if (A[u][v] == 1 && visited[v] == 0)
            {
                printf("Visit %d (neighbor of %d)\n", v, u);
                visited[v] = 1;
                enqueue(q, v);
                printQueue();
            }
        }
    }
}

The full program

All the pieces above, wired together into one file you can compile and run as-is:

#include <stdio.h>
#include <stdlib.h>

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};
int n = 7;

int q[100];
int front = 0, rear = 0;

int isEmpty(int q[])
{
    return front == rear;
}

void enqueue(int q[], int val)
{
    q[rear++] = val;
}

int dequeue(int q[])
{
    return q[front++];
}

void printQueue()
{
    printf("   Queue now: [ ");
    for (int i = front; i < rear; i++)
        printf("%d ", q[i]);
    printf("]\n");
}

void BFS(int start)
{
    printf("Visit %d (start)\n", start);
    visited[start] = 1;
    enqueue(q, start);
    printQueue();

    while (!isEmpty(q))
    {
        int u = dequeue(q);
        printf("Dequeue %d, exploring its neighbors:\n", u);

        for (int v = 1; v <= n; v++)
        {
            if (A[u][v] == 1 && visited[v] == 0)
            {
                printf("Visit %d (neighbor of %d)\n", v, u);
                visited[v] = 1;
                enqueue(q, v);
                printQueue();
            }
        }
    }
}

int main(void)
{
    BFS(1);

    printf("Final BFS order: ");
    for (int i = 0; i < rear; i++)
        printf("%d ", q[i]);
    printf("\n");

    return 0;
}

Output:

Visit 1 (start)
   Queue now: [ 1 ]
Dequeue 1, exploring its neighbors:
Visit 2 (neighbor of 1)
   Queue now: [ 2 ]
Visit 3 (neighbor of 1)
   Queue now: [ 2 3 ]
Visit 4 (neighbor of 1)
   Queue now: [ 2 3 4 ]
Dequeue 2, exploring its neighbors:
Visit 5 (neighbor of 2)
   Queue now: [ 3 4 5 ]
Visit 6 (neighbor of 2)
   Queue now: [ 3 4 5 6 ]
Dequeue 3, exploring its neighbors:
Dequeue 4, exploring its neighbors:
Visit 7 (neighbor of 4)
   Queue now: [ 5 6 7 ]
Dequeue 5, exploring its neighbors:
Dequeue 6, exploring its neighbors:
Dequeue 7, exploring its neighbors:
Final BFS order: 1 2 3 4 5 6 7

The big picture

Before you move on, I want you to notice something.

This code isn't doing anything you haven't already done yourself.

When we traced the graph by hand, you visited a vertex, marked it as visited, and remembered to come back to its neighbors later. The computer is following those exact same steps. The only difference is that it does them much faster — it's just you, but caffeinated. ☕

So if you ever look at BFS code and feel overwhelmed, don't start by reading the syntax.

Instead, ask yourself, "What would I do by hand right now?"

The answer is always the same.

Time Complexity

Before we wrap up, let's talk about the time complexity. (I know, I know — the least fun part of any fun article. Bear with me.)

In this lesson, we stored our graph using an adjacency matrix.

Whenever we explore a vertex, we look across its entire row to check which vertices are connected to it. Even if a vertex has only a few neighbors, we still scan the whole row. Overachiever behavior.

Since we do that for every vertex, the overall time complexity of this implementation is:

If you've come across O(V + E) while learning BFS somewhere else, don't worry — you haven't learned a different algorithm.

The difference is simply in how the graph is stored. In this lesson, we used an adjacency matrix, so the implementation runs in O(V²). Later, when you learn about adjacency lists, you'll see why BFS is often written as O(V + E).

For now, just remember this.

The BFS code we wrote in this lesson has a time complexity of O(V²).

And that's a wrap! 🎬 You made it through BFS — matrix, queue, and all. Go tell someone about neighbors and queues, they'll be thrilled. Probably.