Graph Traversal Made Simple: Your First Guide to BFS & DFS Code (For New Developers)

Forget about nodes, edges, stacks, and queues for now. Let's imagine there's an empty basket, a chocolate cookie (our starting point!), and an empty plate.

All we do in these graph traversals, be it BFS or DFS, is follow a simple process:

1. We pick a cookie from the basket.

2. We find all its directly connected cookies (of different flavors like oats, almond).

3. We put these newly found, unvisited cookies into the basket.

4. We take a bite from the cookie we picked (meaning, we process it).

5. Then, we put this tasted cookie onto our plate.

We repeat this: pick a new cookie from the basket, find its connected cookies, add them to the basket, take a bite from the picked cookie, and add it to the plate which already holds the cookies we've tasted. We keep going until the basket is empty. At the end, we return the plate of tasted cookies, showing the order we visited them.

The only and only difference between BFS and DFS Traversals is in what order we pick the cookies from the basket. This difference in the order of picking cookies from the basket decides how the maze of connections will be traversed: either spreading out (breadth-first) or going deep (depth-first).

Now let's see how the code pulls it off.

First, let's imagine our cookie connections. It's like a map telling us which cookies are next to each other:

// Our yummy cookie connections!

// This is like our graph's adjacency list.

const cookieConnections = {

  'Chocolate': ['Almond', 'Oats'],      // Chocolate cookie is connected to Almond and Oats

  'Almond': ['Chocolate', 'Coconut'], // Almond is connected to Chocolate and Coconut

  'Oats': ['Chocolate', 'Cinnamon'],  // Oats is connected to Chocolate and Cinnamon

  'Coconut': ['Almond'],              // Coconut is connected to Almond

  'Cinnamon': ['Oats']                // Cinnamon is connected to Oats

};


// We'll start our tasting adventure with the Chocolate cookie

const firstCookieToTaste = 'Chocolate';

The Code Setup (Before the Main `while` Loop)

Here we simply set up our basket, the plate, and get ready to taste. We also need a way to remember which cookies we've already seen or put in the basket, so we don't process them again. Let's call this cookiesWeKnow. We then put the first chocolate cookie into the basket and mark it as known.

This setup is almost identical for both BFS and DFS:

function startTasting(connections, startCookie, isBFS) { // Added a parameter to show which function it is for clarity

    let basket = []; // Our basket for cookies to try

    let plate = [];  // Our plate for cookies we've already tasted

    let cookiesWeKnow = new Set(); // To remember cookies we've identified (either in basket or on plate)


    // Put the first chocolate cookie in the basket to kick things off

    if (connections[startCookie]) { // Make sure the starting cookie exists

        basket.push(startCookie);

        cookiesWeKnow.add(startCookie); // Mark it as known

    } else {

        console.log("Starting cookie not found in connections!");

        return plate;

    }

    // ... rest of the traversal logic will go here ...

The Main Tasting Cycle (The While Loop)

This while loop represents the entire cycle of picking a cookie, finding its connected cookies, adding them to the basket, tasting the picked cookie, and putting it on the plate, just like we discussed earlier. It will keep going as long as there are cookies left in the basket.

const currentCookie represents the cookie we have just picked from the basket.

Now here's the first big difference in BFS and DFS code that changes how we traverse the graph: how we pick currentCookie using JavaScript array methods .pop() and .shift().

• Stack Data Structure (DFS) using an array: .pop() takes the last element from the basket array (Last-In, First-Out or LIFO). Think of it as taking a cookie from the top of a pile in the basket.

• Queue Data Structure (BFS) using an array: .shift() takes the first element from the basket array (First-In, First-Out or FIFO). Think of it as taking the cookie that has been waiting the longest in a line in the basket.

In what order we put the cookies in the basket and, crucially, in what order we pick them up to taste, is what decides how the traversal will happen.

Let's see it in context for BFS:

// For BFS:

    while (basket.length > 0) {

        // Pick the cookie from the FRONT of the basket (FIFO)

        const currentCookie = basket.shift(); // Magic for BFS!


        // Take a bite and put it on our plate

        plate.push(currentCookie);


        // Now, let's look for its connected cookies...

        // ... (for loop for neighbors comes next) ...

And for DFS:

JavaScript

// For DFS:

    while (basket.length > 0) {

        // Pick the cookie from the TOP of the basket pile (LIFO)

        const currentCookie = basket.pop(); // Magic for DFS!


        // Take a bite and put it on our plate

        plate.push(currentCookie);


        // Now, let's look for its connected cookies...

        // ... (for loop for neighbors comes next) ...

Finding and Adding Connected Cookies (The For Loop)

Earlier we understood the order in which we pick a cookie from the basket is influenced by .pop() (for DFS) and .shift() (for BFS). Now let's focus on how the newly found connected cookies are added to the basket.

For BFS:

In BFS, after we pick a cookie (using .shift()) and put it on our plate, we find its connected cookies. We then run a straightforward ascending order for loop (from the first connected cookie to the last). If a connected cookie is new to us, we add it to the end of the basket (queue).

// Inside the BFS while loop, after plate.push(currentCookie):

        const connectedCookies = connections[currentCookie] || [];


        // In BFS, we run a straightforward ascending order for loop

        // to find new cookies and add them to the end of the basket (queue).

        for (let i = 0; i < connectedCookies.length; i++) {

            const nextCookie = connectedCookies[i];

            if (!cookiesWeKnow.has(nextCookie)) {

                cookiesWeKnow.add(nextCookie);

                basket.push(nextCookie); // Add to the end (FIFO style)

            }

        }

    } // End of BFS while loop

    return plate;

} // End of BFS tasting function

For DFS:

In DFS, after we pick a cookie (using .pop()) and put it on our plate, we also find its connected cookies. But here's a subtle and important detail: we typically run a reverse for loop (from the last connected cookie back to the first) when adding these cookies to the basket (stack).

Why? This is often done so that the traversal happens from "left-to-right" conceptually, if you imagine the connected cookies listed in a certain order (e.g., if 'Chocolate' is connected to ['Almond', 'Oats'], we want to explore 'Almond' and its path before 'Oats'). Since we use .pop() (Last-In, First-Out) for DFS, if we find neighbors ['Almond', 'Oats'] and add 'Oats' first, then 'Almond' to the basket, 'Almond' will be on top and be picked next. This achieves the "left-to-right" exploration. If we used a forward loop to add them, 'Oats' would be picked first, leading to an (equally valid, but different) "right-to-left" traversal relative to their order in the list.

// Inside the DFS while loop, after plate.push(currentCookie):

        const connectedCookies = connections[currentCookie] || [];


        // In DFS, we run a reverse for loop to add connected cookies to the basket (stack).

        // This ensures that if connections are [A, B], B is pushed, then A is pushed.

        // So, A (the "leftmost" or first in the original list) is on top and gets explored next.

        for (let i = connectedCookies.length - 1; i >= 0; i--) {

            const nextCookie = connectedCookies[i];

            if (!cookiesWeKnow.has(nextCookie)) {

                cookiesWeKnow.add(nextCookie);

                basket.push(nextCookie); // Add to the end, which is the top for .pop()

            }

        }

    } // End of DFS while loop

    return plate;

} // End of DFS tasting function

The Main Difference in a Nutshell

• In simple words, the key difference is that in DFS (Depth-First Search), we keep "piling up" newly found connected cookies, and the next cookie we taste is often one that was very recently added to the top of this pile (because we .pop() the newest). This makes us go deeper and deeper along one path of connections.

• On the other hand, BFS (Breadth-First Search) goes in a more "orderly" fashion. Cookies are picked one-by-one from the beginning of the line in the basket (because we .shift() the oldest). This leads to an equal traversal spread, exploring all cookies at the current "layer" or distance before moving to the next layer.

---

And that's how the code, with just a small change in picking from the basket (and how we strategically add to it for DFS), pulls off two very different ways of exploring our delicious world of cookies!

Let's see the order of tasted cookies for our example:

// To make the functions above runnable, let's wrap them:


// BFS Function

function bfsTraversal(connections, startCookie) {

    let basket = [];

    let plate = [];

    let cookiesWeKnow = new Set();


    if (!connections[startCookie]) return plate;


    basket.push(startCookie);

    cookiesWeKnow.add(startCookie);


    while (basket.length > 0) {

        const currentCookie = basket.shift();

        plate.push(currentCookie);

        const connectedCookies = connections[currentCookie] || [];

        for (let i = 0; i < connectedCookies.length; i++) {

            const nextCookie = connectedCookies[i];

            if (!cookiesWeKnow.has(nextCookie)) {

                cookiesWeKnow.add(nextCookie);

                basket.push(nextCookie);

            }

        }

    }

    return plate;

}


// DFS Function

function dfsTraversal(connections, startCookie) {

    let basket = [];

    let plate = [];

    let cookiesWeKnow = new Set();


    if (!connections[startCookie]) return plate;


    basket.push(startCookie);

    cookiesWeKnow.add(startCookie);


    while (basket.length > 0) {

        const currentCookie = basket.pop();

        plate.push(currentCookie);

        const connectedCookies = connections[currentCookie] || [];

        for (let i = connectedCookies.length - 1; i >= 0; i--) {

            const nextCookie = connectedCookies[i];

            if (!cookiesWeKnow.has(nextCookie)) {

                cookiesWeKnow.add(nextCookie);

                basket.push(nextCookie);

            }

        }

    }

    return plate;

}


console.log("BFS Tasted Order:", bfsTraversal(cookieConnections, firstCookieToTaste).join(', '));

// Expected BFS Output: Chocolate, Almond, Oats, Coconut, Cinnamon


console.log("DFS Tasted Order:", dfsTraversal(cookieConnections, firstCookieToTaste).join(', '));

// Expected DFS Output: Chocolate, Almond, Coconut, Oats, Cinnamon

// (This DFS order explores Chocolate -> Almond -> Coconut fully, then backtracks to Chocolate's other child Oats -> Cinnamon)

Checkout these youtube shorts where a Queue or Stack is the basket, and Processed is the tasted cookies Plate.

For BFS: https://www.youtube.com/shorts/umHJzlKFGlU

For DFS: https://www.youtube.com/shorts/5Kl3L3kdGbs