Implement a Breadth-first Search Function in JavaScript

JavaScript

Share this video with your friends

The breadth-first search is a different kind of search algorithm because it is run against graphs. It is typically used to answer one or both questions, is there a path between point A and point B? As well as, what is the shortest path from point A to point B. It utilizes a queue which is a first in first out data structure. Let’s implement a Breadth-first search function in JavaScript!

Manjunath

~ 6 years ago

This is best explanation that i've ever come across. Thank you so much @tyler.

Roland

~ 6 years ago

Poor Aimee...

Hoang

~ 6 years ago

I implemented it using only one Queue and do not have to maintain another array. Could you guys please have a look. it's working correctly from my side:

const search = (name, bfs = true) => {

    const friends = graph[name];

    console.log(friends);

    let searched = [].concat(friends);

    console.log(searched)

    while (searched.length > 0) {
        const person = searched.shift();

        console.log(person);

        if (person.dog) {
            return `${person.id} has a dog`
        }
        else {
            const personsFriends = graph[person.id];

            console.log(personsFriends)

            if (bfs) {
                searched = searched.concat(personsFriends);
            } else {
                searched = personsFriends.concat(searched)
            }
            

            console.log(searched)
        }
    }

    return `no one has a dog`
}

console.log(search("tyler"))