A Common-Sense Guide to Data Structures and Algorithms

Graphs

A graph is a data structure that specializes in relationships, as it easily conveys how data is connected.

Here is a visualization of our Facebook network:

Each person is represented by a node, and each line indicates a friendship with another person. In graph jargon, each node is called a vertex, and each line is called an edge. Vertices that are connected by an edge are said to be adjacent to each other.

There are a number of ways that a graph can be implemented, but one of the simplest ways is using a hash table (see Chapter 7, ​Blazing Fast Lookup with Hash Tables​). Here’s a bare-bones Ruby implementation of our social network: