A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Chapter 18Connecting 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:

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

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 ...