What is a graph in computer science

Points are things

A graph starts with points. Each point is one thing: a station, a person, a web page, anything at all.
We give each point a name so we can tell which one it is.
There are no lines yet, just points scattered around.

Press an empty spot to place a point. Each point is one thing. (point = node)

The more points you place, the more things there are. But points alone are just scattered dots.
It's like stations standing on their own, which doesn't make a subway map. What's missing is how the points connect to one another.
We'll draw those connections next.

Lines are relationships

Now let's connect the points. Joining two points with a line means "these two are related."
There's a track between two stations, two people are friends, this web page links to that one. Each line is one relationship.
Put points and lines together and you have a graph.

Press one point and then another, and a line appears. Each line is one relationship. (line = edge)

As you draw lines, the points get woven together, and the scattered dots finally become a subway map.
Points are things; lines are relationships. With just these two, you can draw countless things in the world.
Among them hides a shape we already know.

A tree is a special graph

A graph can contain loops. If you start at point A, follow the lines, and come back to A, that's a loop.
A graph with no loops at all is exactly a tree: a shape that only branches outward, with no way back around.
So a tree is one kind of graph.

Press the line that makes the loop to cut it. With the loop gone, it becomes a tree. Tree ⊂ graph.

Cutting one loop removed the way back around, and the tangled-looking graph became a neat tree.
The folders and family trees we saw earlier were trees just like this.
A tree is a special case of a graph; in other words, the graph is the bigger umbrella.

Graphs are everywhere

Put on the glasses of points and lines, and the world looks different.
The subway is stations (points) and routes (lines), a friend network is people (points) and friendships (lines), and the web is pages (points) and links (lines).
Things that seemed completely different were really the same picture. So solve one, and you've solved the others too.

Press an example to switch. Subway, friend network, web: all the same points and lines.

Switching examples doesn't change the skeleton of the picture. Points are things, lines are relationships; only the labels change.
That's exactly why graphs are so useful: a single tool can draw countless problems in the world.

Summary

In one line: points are things, lines are relationships, and a picture drawn with points and lines is a graph. A special graph with no loops is a tree.
Subways, friend networks, and the web can all be drawn with points and lines.
Now that the points and lines are in place, one question remains: how do we move around between these points?

Press the key points in order to review. (point = thing → line = relationship → graph → a tree is a graph with no loops)

Now that you can draw graphs, the real fun begins.
Starting from one point and following the lines to visit every point is called graph traversal, and finding the shortest route comes after that.
In the next lesson, we'll follow how to move across points and lines.