Chapter 18
Connecting Everything with Graphs

Let’s say we’re building a social network that allows people to be friends with one another. These friendships are mutual, so if Alice is friends with Bob, then Bob is also friends with Alice.

How can we best organize this data?

One basic approach might be to use a two-dimensional array that stores the list of friendships:

Here, each subarray containing a pair of names represents a friendship between two people.

Unfortunately, with this approach, there’s no quick way to see who Alice’s friends are. If we look carefully, we can see that that Alice is friends with Bob, Diana, and Fred. But for the computer to determine this, it would have to comb through all the relationships in the list, since Alice can be present in any of them. This is O(N), which is very slow.

Thankfully, we can do much, much better than this. With a data structure known as a graph, we can find Alice’s friends in just O(1) time.