friends of friends

say you grow mangoes and need someone to sell them. you'd start with your friends: does any of them sell mangoes? if not, you'd ask about their friends, then their friends' friends. and you'd want the closest seller you can find: a friend before a friend of a friend.

that's a graph problem, and the answer is breadth-first search.

#graphs

in code, a graph is usually a hash table from each node to its neighbors:

const graph = {
  you: ['alice', 'bob', 'claire'],
  alice: ['peggy'],
  bob: ['anuj', 'peggy'],
  claire: ['thom', 'jonny'],
  anuj: [],
  peggy: [],
  thom: [],
  jonny: [],
};

the edges here only go one way: you're in nobody's list. that's a directed graph.

#breadth-first

what keeps the order is a queue: first in, first out. take a person off the front and check them. if they don't sell mangoes, add their friends to the back. everyone in the first ring was added before anyone in the second, so they all get checked first.

swap the queue for a stack (last in, first out) and you get depth-first search, which follows one chain of friends as far as it goes before trying the next. it finds a seller, but not necessarily the closest one.

#in code

const sellsMangoes = (name) => name === 'thom';
 
function closestSeller(graph, start) {
  const queue = [start];
  const cameFrom = new Map([[start, null]]);
 
  while (queue.length) {
    const person = queue.shift();
    if (person !== start && sellsMangoes(person)) {
      const path = [];
      for (let at = person; at; at = cameFrom.get(at)) path.unshift(at);
      return path;
    }
    for (const friend of graph[person]) {
      if (!cameFrom.has(friend)) {
        cameFrom.set(friend, person);
        queue.push(friend);
      }
    }
  }
 
  return null;
}
 
closestSeller(graph, 'you'); // ['you', 'claire', 'thom']

cameFrom does two jobs. it remembers who's already been queued, so Peggy, who's friends with both Alice and Bob, only gets checked once. and it remembers how each person was reached, so once Thom turns up, walking back through it gives the path.

#the slow version

the first version of this code kept the people it had checked in an array, and asked checked.includes(person) before every check. it also built a new queue with concat every time it added someone's friends. both look harmless, and both go through the whole list every time.

on a graph of 20,000 people with 5 friends each, with no seller anywhere, so it had to check everyone: that version took 20.2 seconds. the one above took 9.5ms. a Map answers "seen them yet?" in constant time, and push doesn't copy anything.

done right, breadth-first search looks at every person once and every friendship once: O(V + E), nodes plus edges.

#where it comes from

Konrad Zuse came up with it in 1945, in a PhD thesis that was rejected and only published in 1972. Edward F. Moore came up with it again in 1959, to find the shortest way out of a maze. when the edges have different lengths, like roads in minutes, the rings stop working, and you need Dijkstra's algorithm.