Chapter
13
Connecting 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 array, and check to see whether Alice is contained within the relationship. By the time we get through the entire array, we’d create a list of all of Alice’s friends (who happen to be Bob, Diana, and Fred). We’d also perform the same process if we wanted to simply check whether Elise was Alice’s friend.
Based on the way we’ve structured our data, searching for Alice’s friends would have an efficiency of O(N), since we need to inspect every relationship in our database.
But we can do much, much better. With a data structure known as a graph, we can find each of Alice’s friends in just O(1) time.