What is a graph data structure

Holding relationships with dots and lines

So far we have seen how to hold values in rows, tables, and trees. But for some data, the relationships between values matter more than the values themselves: who is friends with whom, or which station connects to which.
In such cases, lining things up in a row feels awkward. So you draw people as dots and friendships as lines. Dots are also called nodes and lines are called edges, and the relationships are held exactly as they are, with nothing but dots and lines.

Tap two people in turn to join them with a line. A dot is a person; a line is a friendship.

Joining the dots made the relationships visible. Who is connected to whom is clear the moment you look at the lines, far more vivid than rows written in a table.
Dots are things, lines are relationships, and data held with these two is called a graph. A two-way relationship like friendship is drawn as a line with no direction, while a one-way relationship, like one person following another, is drawn as an arrow. So what can you learn by following these lines?

Along the lines to a friend of a friend

Start from one person. Follow the lines attached to that dot and you reach that person's friends. Don't stop there: follow the lines attached to the friends' dots and you reach the friends of friends.
Going one step further each time like this, you reach the people your acquaintances know. When a social service suggests "people you may know," it works this way.

Tap one person and their friends light up; tap again and the friends of friends light up next.

One tap lit up the friends, and another lit up the friends of friends. How far someone is from the starting person depends on how many lines you crossed.
Cross one line and it is a friend; cross two and it is a friend of a friend. With a table, you would have dug through it again and again to work this out. Following lines makes it this easy.

Following neighbors around a group

The dots joined directly to a dot by a line are called its neighbors. Let's keep spreading out along the lines: from one dot to its neighbors, and then to their neighbors.
Sooner or later there is nowhere left to go. The dots reached by then form one connected group. A dot not joined by any line does not belong to that group. Widening the search one layer of neighbors at a time, starting from the closest, is called breadth-first search.

Tap a neighbor at the edge of the lit group to spread it out one step at a time. Only connected dots light up.

Spreading along the neighbors lit up the connected dots one after another. You could visit every place the lines reach, while a separate dot never lit up, however far you went.
Whether dots are joined by lines is what divides them into groups. In a graph, following neighbors is easy, because you just look at the lines. So what if you did the same job with a table?

Table or graph?

Suppose friendships are written in a table. To find friends of friends, you first find your own friends in the table and write them down, then dig through the table again for each of those friends. Every step further means scanning the table once more.
With a graph, you follow the lines from a dot, then follow the lines from the next dots, and you are done. When relationships are the point, a graph is far more convenient.

Solve the same "friends of friends" question with a table and with a graph. Compare how many taps each takes.

The table took far more taps to find the same answer, because the lookups had to be repeated. The graph was done after following lines twice.
Of course, tables are not bad. For recording things row by row and collecting them, a table works well. But for following relationships, a graph of dots and lines is far more natural and faster. When a map app finds a route, it too uses a graph, with stations and roads as dots and lines and a distance written on each line.

Summary

In short: holding things as dots and relationships as lines gives you a graph. Following the lines from a dot gives you its neighbors, and following the neighbors' lines gives you friends of friends.
Spreading along the lines reveals the connected group. For jobs where relationships are the point, instead of digging through a table many times, you just follow the lines. Dots=things, lines=relationships, and following neighbors: that is a graph.

Tap the key points in order to review. (dots=things, lines=relationships → friends of friends → following neighbors → graphs for relationships)

Now you know how to hold relationships as dots and lines and travel along them. Friends of friends, awkward to find in a table, were just two lines away in a graph. Depending on the shape you give the data, the same job can become easy or hard.
But to ask a database anything, you have to ask in a set language. The next lesson teaches the language for asking a database questions: SQL.