# friends of friends

2024-02-25 · 4 min read · #algorithms · #graphs · #data-structures

Source: https://jopcmelo.com/writing/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

a graph is a set of things and the connections between them. the things are called nodes (or vertices), and the connections are edges. you and your friends are nodes, and "is friends with" is an edge.

in code, a graph is usually a [hash table](/writing/constant-time-most-of-the-time) from each node to its neighbors:

```javascript
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

breadth-first search checks everyone one step away before anyone two steps away, then everyone two steps away before anyone three. **it spreads out in rings**, so the first seller it finds is one of the closest.

*(sketch: you in the middle, your friends Alice, Bob and Claire around you, and their friends Peggy, Anuj, Thom and Jonny further out. a ripple goes out from you, lighting up your friends first, then theirs. Thom sells mangoes, and stays lit)*

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.

*(sketch: a queue of Alice, Bob and Claire. the one at the front gets checked next, and Bob's friends join at the back)*

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

```javascript
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](https://en.wikipedia.org/wiki/Breadth-first_search). when the edges have different lengths, like roads in minutes, the rings stop working, and you need [Dijkstra's algorithm](/writing/rotterdam-to-groningen).