A Common-Sense Guide to Data Structures and Algorithms

Chapter 13Connecting Everything with Graphs

Let’s say that we’re building a social network such as Facebook. In such an application, many people can 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 very simple approach might be to use a two-dimensional array that stores the list of friendships:

relationships = [
  ["Alice", "Bob"],
  ["Bob", "Cynthia"],
  ["Alice", "Diana"],
  ["Bob", "Diana"],
  ["Elise", "Fred"],
  ["Diana", "Fred"],
  ["Fred", "Alice"]
]

Unfortunately, with this approach, there’s no quick way to see who Alice’s friends are. We’d have to inspect each relationship within the ...