JavaScript breadth-first search algorithm

Question

I have implemented a breadth-first search and I'm more or less looking for suggestions on how I can improve on what I've done here.

How to use:

search(queue, "Musician");

The logs from the search:

Lansana is not a Musician. Lansana is a Software Engineer.
Zack is not a Musician. Zack is a Software Architect.
John is not a Musician. John is a Project Manager.
Francisco is not a Musician. Francisco is a Game Developer.
Ronaldinho is not a Musician. Ronaldinho is a Professional Soccer Player.
Lauren is not a Musician. Lauren is a Mango Seller.
Angelica is not a Musician. Angelica is a Professional Volleyball Player.
Cody is not a Musician. Cody is a Network Programmer.
Match found: Beyonce is a Musician!

I believe it works correctly because if you look at the order in which I enqueue people, and the order in which their friends are enqueued, you'll notice that the logs match the exact order (which of course is crucial in this algorithm in order to get the shortest path).

class Queue {
    constructor() {
        this.count = 0;
        this.data = {};
    }

    enqueue(key, val) {
        if (!this.data.hasOwnProperty(key)) {
            this.count++;
        }
        this.data[key] = val;
    }

    dequeue() {
        let key = Object.keys(this.data)[0],
            memo = this.data[key];
        delete this.data[key];
        this.count--;
        return memo;
    }
}

class Person {
    constructor(args) {
        this.name = args.name;
        this.friends = args.friends || [];
        this.profession = args.profession;
    }
}

let Ronaldinho = new Person({
        name: "Ronaldinho",
        profession: "Professional Soccer Player"
    }),
    Lauren = new Person({
        name: "Lauren",
        profession: "Mango Seller"
    }),
    Angelica = new Person({
        name: "Angelica",
        profession: "Professional Volleyball Player"
    }),
    Cody = new Person({
        name: "Cody",
        profession: "Network Programmer"
    }),
    Beyonce = new Person({
        name: "Beyonce",
        profession: "Musician"
    }),
    Lansana = new Person({
        name: "Lansana",
        friends: [Ronaldinho, Lauren, Angelica],
        profession: "Software Engineer"
    }),
    Zack = new Person({
        name: "Zack",
        friends: [Cody],
        profession: "Software Architect"
    }),
    John = new Person({
        name: "John",
        friends: [Ronaldinho, Angelica],
        profession: "Project Manager"
    }),
    Francisco = new Person({
        name: "Francisco",
        friends: [Beyonce],
        profession: "Game Developer"
    });

let queue = new Queue();

queue.enqueue("Lansana", Lansana);
queue.enqueue("Zack", Zack);
queue.enqueue("John", John);
queue.enqueue("Francisco", Francisco);

function search(queue, profession) {
    let searched = [];

    while (queue.count > 0) {
        let person = queue.dequeue();

        if (!searched[person.name]) {
            if (hasProfession(person, profession)) {
                console.log(`Match found: ${person.name} is  a ${person.profession}!`);
                return true;
            } else {
                console.log(`${person.name} is not a ${profession}. ${person.name} is a ${person.profession}.`);
                for(let i = 0, len = person.friends.length; i < len; i++) {
                    queue.enqueue(person.friends[i].name, person.friends[i]);
                }
            }

            searched.push(person.name);
        }
    }

    return false;
}

function hasProfession(person, profession) {
    return person.profession.toLowerCase() === profession.toLowerCase();
}

Answer 1

Just going to make a few comment on your Queue implementation.

Should your data be an object this.data = {};?

This is a matter of taste, but I would have opted for an array or a linkedlist data structure if I were you. Using an array, you can easily push items without a key . From my perspective ,you are basically passing the same name for the key/value pair in the enqueue.

How to retrieve the total number of items enqueued?

I believe your class should data should only be private to your class. hence the data count should be accessed using a getter function e.g

this.count = function() {
    return this.data.length;
  };

What should your enqueue look like?

basically, your Queue class is not reusable as it's dependent on having key/value pair has an input. I reckon the enqueue function should take only one value . In this case John. A pseudocode

    enqueue(value) {
      // created an empty if statement - note if value is undefined this will evaluate to true as well as null ==null
      if (value == null);
      else {
        if ( //data enqueued has exceeded the current array length) {
          let newcapacity = Math.floor(this.count() * this.growfactor / 100);
          // create a new array with the capacity and copy the old array elements to a new one.
        }

        this.size++;
        // assign the item to an empty index 
        this.data[index] = value;
      }
    }
    }

Although, the above is more or less a C# equivalent but the main idea is you only enqueue items when they are not null/undefined - hence I used == as opposed to === as undefined== null results in true and null==null results in true . This is equivalent to

if ( typeof(some_variable) !== "undefined" && some_variable !== null ) {}

The newCapacity is simply a strategy to increase the size of an array.

How to easily delete an item using an array?

Constantly, you need to check if your array's size is zero then throw an exception else call the array's shift() function to delete the first item and update the array.

dequeue() {
  if (size === 0) {
    throw "the queue contains no items";
  }
  this.data.shift();
}

Note: there are some very useful Queue functions that can be added to your class :

• peek() : returns the first item in the queue
• contains : Check if an item exist
• isempty()- checks if an item is empty

I hope this helps.