What a graph is

A graph is nothing more than a set of things and the connections between them. The things are called nodes and the connections are called edges, and once you have those two words you have the whole idea. A graph is the natural shape for anything whose meaning lives in how its parts relate to each other rather than in the parts alone.

Two words, and that is all

Start with the smallest possible version. Draw a few dots on paper. Now draw some lines between the dots. That drawing is a graph. The dots are nodes, sometimes called vertices. The lines are edges. There is no third ingredient. Every graph you will ever meet, no matter how large, is just nodes and the edges between them.

The reason this tiny idea matters is that it fits so much of the world. Think of people and who is friends with whom. Each person is a node. Each friendship is an edge between two people. Think of cities and the roads that connect them. Each city is a node. Each road is an edge. Think of web pages and the links between them. Each page is a node. Each link from one page to another is an edge. The same picture keeps appearing because the same situation keeps appearing: separate things, joined by relationships.

What makes a graph a graph, rather than just a list of things, is that the edges are first class. In a graph you care as much about the connections as about the items. A friend list that only told you the names of people, with no record of who knows whom, would be missing the entire point. The point is the who knows whom. The edges are where the meaning is.

Edges can point, or not

The first real distinction between graphs is whether the edges have a direction. Friendship usually does not. If you are my friend, I am your friend. The edge runs both ways at once, so we draw it as a plain line. A graph whose edges work like this is called an undirected graph. Roads between cities are often undirected too, since you can drive either way down most of them.

Plenty of relationships are one way, though. On many social sites you can follow someone who does not follow you back. That following is a directed relationship: it runs from you to them, and not automatically the other way. We draw it as an arrow. A graph whose edges carry arrows is called a directed graph. Web links are directed: page A can link to page B without page B linking back. So is the relationship of one person being another person’s manager, or one task having to finish before another can start.

The difference is not a technicality. It changes what you can ask. In an undirected friend graph, if you can reach a person, they can reach you by the same edges. In a directed follow graph, the fact that you can reach a celebrity by following the arrows tells you nothing about whether they can reach you. Direction is information, and throwing it away when the relationship really is one way would quietly give you wrong answers.

Edges can carry a number

So far every edge has been the same as every other edge: present or absent, and nothing more. But often the connections differ in strength or cost, and we want to record that. We do it by attaching a number to each edge. A graph whose edges carry numbers is called a weighted graph, and the number is the edge’s weight.

Roads are the easy example. The cities are the nodes, the roads are the edges, and the weight on each road might be its length in miles, or how long it takes to drive, or the toll it costs. Now the graph holds more than just what connects to what. It holds how far, or how long, or how expensive. In a friend graph the weight might be how often two people talk, so a close friendship is a heavy edge and a distant acquaintance is a light one. The weight lets a single graph describe not only the structure but the varying importance of the links inside it.

Nodes are the things. Edges are the relationships. Direction says whether a relationship runs one way or both, and weight says how strong or costly it is. Everything else is built from these.

Neighbors, paths, and walking

Once you have nodes and edges you get a few more ideas for free, and these are the ideas that make graphs useful rather than merely tidy. The first is a node’s neighbors. The neighbors of a node are simply the other nodes it connects to directly by one edge. Your neighbors in a friend graph are your immediate friends. A city’s neighbors are the cities one road away. In a directed graph you have to be careful about which way the arrows go: the nodes you point to and the nodes that point to you can be two different sets, and often you want to ask about each separately.

The second idea is a path. A path is a sequence of edges that takes you from one node to another, hopping from neighbor to neighbor. To get from your home city to a city on the far coast you might pass through four cities on the way. That sequence of roads is a path. In a friend graph, a path from you to a stranger is the chain of mutual acquaintances that links you: your friend, who knows someone, who knows the stranger. The famous idea that any two people are separated by a small number of such hops is a claim about paths in the graph of human acquaintance.

The third idea is the act of moving through the graph, which is usually called walking or traversing it. You start at some node, look at its neighbors, step to one of them, look at its neighbors, and keep going. This sounds simple, and it is, but nearly every interesting question about a graph is answered by some careful version of this walk.

Suppose you want everyone reachable from a starting person through friendships, no matter how many hops away. You walk. Visit the start, then all of its neighbors, then all of their neighbors that you have not already seen, and so on, keeping a note of who you have already visited so you never go in circles. When you run out of new nodes to visit, the set of nodes you touched is exactly the reachable set. The same walk, run on a road map with weights, and with a rule that always extends the cheapest path so far, finds the shortest route between two cities. The graph is static, but walking it is how you extract answers from it.

Why this is the right shape for relationships

It is worth being concrete about why the graph is the correct model when relationships are the point, rather than just one option among many. The reason is that a graph makes the relationships into things you can name, count, follow, and reason about directly. If your question is a question about connection, then a structure that stores connections as first class objects lets you ask that question straight, instead of reconstructing the connections every time from something that does not really hold them.

Almost every question that begins with a relationship is a graph question in disguise. What connects to this? What does this connect to? Is there any way to get from here to there, and if so, what is the shortest one? What forms a tight cluster where everything links to everything else? Which single node, if you removed it, would split the whole thing into disconnected pieces? Every one of those is answered by looking at nodes and edges and walking between them. If you had stored your information in a shape that hid the edges, you would have to rebuild them before you could even start.

The contrast: a flat list or a table

To see why the shape matters, compare it with the two most common ways people store information: a flat list and a table. A flat list is just items in a row, one after another, with no recorded relationships between them. A shopping list is a flat list. It is perfect when the items truly are independent and order barely matters. It is useless the moment you care how the items relate, because it simply does not record that.

A table is one step up. It is rows and columns, like a spreadsheet: each row is one item, each column is one of its attributes. A table of people might have a name column, an age column, and a city column. Tables are excellent for attributes of individual things. They start to strain the moment the important information is a relationship between two rows.

Picture that people table and the question, who is friends with whom. A table wants to answer with columns, but friendship is not an attribute of one person. It is a link between two of them, and a person can have any number of friends. You end up bolting on a second table that does nothing but list pairs of people who are connected, one pair per row. That second table is, quietly, a list of edges. You have rebuilt a graph inside a format that was not designed for it. And the questions that a graph answers by walking, such as friends of friends, or the shortest chain between two strangers, become slow and awkward in table form, because each hop means matching the whole pair table against itself again.

This is the crux. A flat list forgets relationships entirely. A table can bolt them on but pays for every hop. A graph is the format where a relationship is a native object you can hold, follow, and count. When relationships are rare and incidental, a list or a table is the simpler and better choice, and you should use it. When relationships are the whole point, the graph is not a clever trick. It is just the honest shape of the data.

A table answers questions about things. A graph answers questions about how things are connected. Choose the one that matches the question you actually have.

The same idea, scaled up

Everything so far has used graphs you could draw on a napkin: a dozen friends, a handful of cities. Nothing changes about the definition when the graph gets large. A graph of a country’s road network has millions of nodes and edges, but it is still cities and roads, still walked the same way. A graph of the pages on the public internet has billions of nodes, but the shortest chain of links between two pages is found by the same walk you would use on five pages. The idea does not get more complicated as it grows. It only gets bigger, and the walks take longer.

That is why the graph turns up again and again once you start looking. Anywhere you find separate things joined by relationships that carry meaning, you find a graph, whether or not anyone has drawn it. The relationships were already there. Naming them as nodes and edges is what lets you work with them instead of merely sensing that they exist.

Where this leads

The reason all of this appears in a hub about software is that a codebase is one of the purest examples of the pattern. The pieces of a program are separate things, and the relationships between them, one function calling another, one file importing another, one service sending a request to another, are exactly the connections that carry the meaning and cause the trouble. Storing those connections as a graph turns a pile of files into something you can walk.

When the nodes are the declarations in your source code and the edges are the real relationships between them, the graph has a specific name: the code knowledge graph. Two particular slices of it are important enough to have their own names. When the edges are function calls, it is the call graph. When the edges are the imports and packages that make one unit of code rely on another, it is the dependency graph. Those are the next ideas to walk to from here, and now that you know what a graph is, each of them is just this same picture pointed at code.