bfs_example.js

class Person {
  name: string;
  friends: Array<Person>;
  
  constructor(name: string) {
    this.name = name;
    this.friends = [];
  }

  addFriends(friends: Array<Person>) {
    for (const friend of friends) {
      if (!this.friends.includes(friend)) {
	    this.friends.push(friend);
      }
      
      if (!friend.friends.includes(this)) {
        friend.friends.push(this);
      }
    }
  }
  
  getFriends() {
    return this.friends;
  }
  
}

// friends: bob, diane
const alice = new Person("alice");

// friends: alice, charles, emmett
const bob = new Person("bob");

// friends: bob, frank
const charles = new Person("charles");

// friends: alice, frank
const diane = new Person("diane");

// friends: bob, frank
const emmett = new Person("emmett");

// friends: diane, charles, emmett
const frank = new Person("frank");

const gina = new Person("gina");
const hubert = new Person("hubert");

alice.addFriends([bob, diane]);
bob.addFriends([alice, charles, emmett]);
charles.addFriends([bob, frank]);
diane.addFriends([alice, frank]);
emmett.addFriends([bob]);
frank.addFriends([diane, charles]);
gina.addFriends([hubert]);


class Node<T> {
  value: T;
  parent: ?Node<T>;
  children: Array<Node<T>>;
  
  constructor(value: T, parent: ?Node<T>) {
    this.value = value;
    this.parent = parent;
    this.children = [];
  }

  setChildrenWithValues(children: Array<T>) {
    this.children = this.children.concat(
	  children.map(child => new Node(child, this))
    );
  }
  
}

// BFS to find shortest path from Alice-Frank
const shortestPath = (start: Person, goal: Person): Array<Person> => {
  if (start === goal) {
    const startNameArray = [start];
  }

  let visited: Array<Person> = [];

  let goalNode: ?Node<Person>;

  // Construct tree with root == `start`, via BFS
  const startNode: Node<Person> = new Node(start);
  let nodeQueue: Array<Node<Person>> = [startNode];

  while (nodeQueue.length > 0) {
    const currentNode = nodeQueue.shift();
    visited.push(currentNode.value);

    if (currentNode.value == goal) {
      goalNode = currentNode;
      break;
    }
    const friends = currentNode.value.getFriends();

    // ES5 Set doesn't have a "subtract" set operation
    const unseenFriends = [...friends].filter(friend => !visited.includes(friend))

    // Set children
    currentNode.setChildrenWithValues(unseenFriends);
    nodeQueue = nodeQueue.concat(currentNode.children);
  }
  
  if (goalNode == null) {
    return [];
  }

  // Construct path from start - goal
  let path = [goalNode.value.name];

  let parent: ?Node<Person> = goalNode.parent;
  while (parent != null) {
    path.unshift(parent.value.name);
    parent = parent.parent;
  }
  
  return path;
};


console.log(shortestPath(alice, hubert));

// Leave this here to make sure console logs don't get obscured by horizontal scroll.
console.log("\n\n");