The Graph: How Software Models Maps, Friends, and the Web

You open a social app and under a stranger's name it quietly says 12 mutual friends. You tap your maps app and it threads a route through a thousand intersections. Your laptop installs one small tool and silently pulls in nine other packages first — in exactly the right order, never the wrong one.

Three different apps, and underneath all three sits the same idea, drawn as dots and lines. That idea is the graph — the most flexible data structure you'll ever meet, and the one that models the messy, connected real world better than any list or tree. By the end of this article you and I will have built one together, stored it two different ways, and known exactly when to reach for each.

Let's start nowhere near a computer

Forget code. Picture six friends at a reunion — Ana, Ben, Cy, Dev, Eli, and Fin. Some of them know each other, some don't. Your job is to write down who knows whom, so a newcomer can look anyone up.

There are exactly two natural ways to do it — and this is the whole article — real software uses both.

Way one: give everyone a contacts page. Ana's page lists the people she knows: Ben, Cy. Ben's page lists Ana, Cy. Dev's page just says Eli. To answer "who does Ana know?", you flip to her page and read it off. Short, personal, and it only ever mentions friendships that actually exist.

Way two: pin one big grid to the wall. Six names down the side, the same six across the top, and a tick in a cell whenever those two people know each other. To answer "do Ana and Fin know each other?", you find Ana's row, slide across to Fin's column, and read the single cell where they meet. Instant — but the grid reserves a box for every possible pair, all 36 of them, even though most stay stubbornly empty.

Hold onto those two pictures, because the entire article lives between them. The contacts page is called an adjacency list. The wall grid is called an adjacency matrix. Almost every decision you'll make about a graph comes down to which of the two you'd rather keep.

You already think in graphs

Once you see dots-and-lines, you'll spot graphs everywhere you look:

• Your friends. People are vertices, friendships are edges. "Mutual friends" and "people you may know" are just questions about which dots share neighbours.
• Maps. Places are vertices, roads are edges — and each road carries a number (distance, time), so this graph is weighted.
• The web. Every page is a vertex, every hyperlink an edge pointing one way. Google's original ranking read the whole web as one enormous graph.
• Dependencies. Task B needs A finished first — an edge pointing from A to B.

That last one is worth slowing down on, because it shows how a tiny twist on "dots and lines" quietly runs your machine. When your package manager installs a library, that library needs others, which need others still — a graph of directed edges ("this needs that"). And it must be acyclic: if A needs B and B needs A, nothing can go first, and the installer throws the dreaded circular dependency error. The same shape is your build system deciding compile order, a spreadsheet deciding which cells to recalculate, and a university deciding course prerequisites. Walking such a graph so that every prerequisite lands before the thing that needs it is called a topological sort — and, as you'll see, it's nothing more than a careful graph traversal. The dots-and-lines never changed; we just aimed the lines and forbade loops.

What a graph actually looks like

Here's our six-friend reunion drawn out. Two little clusters — a triangle who all know each other on the left, a chain on the right:

Three words, and you speak graph:

• A vertex (or node) is a dot — a person, a place, a web page.
• An edge is a line — a relationship between two vertices.
• The degree of a vertex is how many edges touch it. Ana has degree 2 (Ben and Cy); Fin has degree 1 (just Eli).

Here's a small, satisfying fact hiding in that last bullet. Add up every vertex's degree and you always get exactly twice the number of edges — because each edge, having two ends, adds 1 to the degree of both. Our graph has 5 edges, and the degrees 2 + 2 + 2 + 1 + 2 + 1 = 10. That's the handshake lemma, and it's the reason an adjacency list's total size is V + 2E rather than something scarier.

The dials every graph sets

Before we store anything, know that "graph" is really a family. Every graph sets a few dials, and those dials decide what your code must do.

Directed or undirected? A friendship goes both ways — if Ana knows Ben, Ben knows Ana. A follow, or a one-way street, or a "needs first", goes only one way. That single choice ripples through everything:

Weighted or unweighted? An unweighted edge just says "these two connect." A weighted edge carries a number — the kilometres between two towns, the price of a trade, the strength of a tie:

Cyclic or acyclic? Can you leave a vertex and, following edges, arrive back where you started? A friendship graph is happily full of cycles. A dependency graph must have none — a directed graph with no cycles is a DAG, and it's the shape behind build order, task scheduling, and version histories.

Connected or not? Our reunion has two separate circles that share nobody — so it's disconnected, with two pieces. Counting those pieces is a job we'll write code for shortly.

For the build, we'll take the friendliest common case — undirected and unweighted — and I'll show you exactly where each dial changes a single line.

Let's build one, step by step

Step 1: the adjacency list — a contacts page per vertex

We'll number our friends 0..5 (Ana = 0, Ben = 1, and so on — computers love dense integer ids) and give each one a list of the neighbours it connects to. An array of lists, one slot per vertex, is the whole structure:

public final class Graph {
    private final int vertexCount;
    private final List<List<Integer>> adjacency;
 
    public Graph(int vertexCount) {
        this.vertexCount = vertexCount;
        this.adjacency = new ArrayList<>();
        for (int v = 0; v < vertexCount; v++) {
            adjacency.add(new ArrayList<>());   // an empty page per vertex
        }
    }
}

adjacency.get(0) is Ana's contacts page. Right now everyone's page is blank — nobody knows anybody yet.

Step 2: addEdge — and the one-way bug that bites everyone

To record "Ana knows Ben", we add Ben to Ana's page. Easy. Let's write the obvious version and watch it go wrong:

public void addEdge(int u, int v) {
    adjacency.get(u).add(v);   // u now knows v...
}                              // ...but v still has no idea about u!

Run addEdge(0, 1) and then ask neighbors(1) — Ben's page is empty. We wrote the friendship on Ana's page only. We meant an undirected edge, but we accidentally built a directed one. And it's a silent bug: small graphs still look plausible, but a traversal starting at Ben never reaches Ana, so counting the friend-circles gives the wrong answer.

The dial from earlier is the fix. An undirected edge is really two directed ones, so write it on both pages:

/** Undirected edge: u knows v and v knows u. O(1). */
public void addEdge(int u, int v) {
    adjacency.get(u).add(v);
    adjacency.get(v).add(u);   // the line the buggy version forgot
}

That second line is the "directed vs undirected" dial. Building a directed graph? Delete it, and an edge points only one way. Everything else in the class stays identical.

Step 3: neighbors and degree — the questions a list is built for

With edges in place, two questions become almost free. "Who does u connect to?" hands back its page. "How many edges touch u?" is the length of that page.

/** The vertices directly connected to u. */
public List<Integer> neighbors(int u) {
    return adjacency.get(u);
}
 
/** How many edges touch u. */
public int degree(int u) {
    return adjacency.get(u).size();
}

This is the adjacency list's whole reason for living: to list a vertex's neighbours, you touch only its real neighbours — nothing else. Ana has 2 friends, so neighbors(0) does 2 units of work, not 6. Hold that thought; in a moment the grid will do it very differently.

Step 4: the other way to store it — the adjacency matrix

Now the wall grid. Same six friends, but instead of pages we keep one V × V table of booleans: connected[u][v] is true exactly when there's an edge.

public final class MatrixGraph {
    private final boolean[][] connected;
 
    public MatrixGraph(int vertexCount) {
        this.connected = new boolean[vertexCount][vertexCount];
    }
 
    /** Undirected → mirror the tick across the diagonal. O(1). */
    public void addEdge(int u, int v) {
        connected[u][v] = true;
        connected[v][u] = true;
    }
 
    /** Is there an edge between u and v? O(1) — one array lookup. */
    public boolean hasEdge(int u, int v) {
        return connected[u][v];
    }
 
    /** u's neighbours — but now we must scan a whole row. O(V). */
    public List<Integer> neighbors(int u) {
        List<Integer> result = new ArrayList<>();
        for (int v = 0; v < connected.length; v++) {
            if (connected[u][v]) {
                result.add(v);
            }
        }
        return result;
    }
}

Look at the two neighbour methods side by side and you've found the heart of the whole trade-off. The list's neighbors touches only real friends. The matrix's neighbors has to walk the entire row — all V cells — because it has no idea which ones hold a tick until it looks. But in exchange, the matrix answers hasEdge in a single step: no scanning, just connected[u][v]. The list has to riffle through u's page to answer that same question.

Notice, too, that the undirected dial shows up here as symmetry: because we set both [u][v] and [v][u], the grid is a mirror image across its diagonal. A directed graph would set just one, and the symmetry would break.

Step 5: counting connected components — a flood per circle

"How many separate friend-circles are there?" is the classic first real question you ask a graph. The idea is beautifully simple: start at any vertex you haven't seen and flood outward to everything reachable from it — that whole flood is one component. When the flood dies, look for any vertex it never touched; if one exists, it belongs to a brand-new circle, so bump the count and flood again.

The flood itself is a breadth-first search — the same "spread out one ring at a time" idea you'd see in Dijkstra's algorithm, minus the weights. A queue holds the frontier; we mark a vertex the moment it enters the queue.

/** How many separate connected pieces the graph has. O(V + E). */
public int connectedComponents() {
    boolean[] seen = new boolean[vertexCount];
    int components = 0;
    for (int start = 0; start < vertexCount; start++) {
        if (!seen[start]) {
            components++;      // a vertex nobody reached — a new circle
            bfs(start, seen);  // flood everything it can reach
        }
    }
    return components;
}
 
private void bfs(int start, boolean[] seen) {
    Queue<Integer> queue = new ArrayDeque<>();
    seen[start] = true;                 // mark on ENQUEUE, not on dequeue
    queue.add(start);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adjacency.get(u)) {
            if (!seen[v]) {
                seen[v] = true;
                queue.add(v);
            }
        }
    }
}

The outer loop is the other half people forget: without it you'd flood from vertex 0, reach Ana's whole circle, and stop — happily reporting "1 component" while Dev, Eli, and Fin sit unvisited on the other side of the room. A single traversal only ever sees one component. To see them all, you must be willing to start a fresh flood from every vertex the previous floods missed.

How much does each really cost?

Here's the whole decision in one table. Call the number of vertices V, the number of edges E, and remember that degree(u) — the length of one page — is tiny compared to V when the graph is sparse.

Read the last row twice, because it's the one that decides real systems. A traversal with a list visits each vertex once and walks each edge twice (the handshake lemma again) — O(V + E), and not a step more. The same traversal on a matrix must scan a full row of V cells at every vertex just to find the neighbours, so it costs O(V²) no matter how few edges exist. On a graph with a million vertices and only a few million edges, that's the difference between milliseconds and never finishing.

The one hard question: when does the grid actually win?

So why does the matrix exist at all? Because "space" and "speed" flip completely once a graph gets dense, and understanding that flip is what separates a memorised answer from a real one.

Think about the two extremes on V = 1000 vertices. A bit-matrix always costs the same V² bits — one per possible pair — whether the graph is nearly empty or nearly full. A list, though, costs roughly 2E entries, and each entry is a whole machine word (call it 32 bits), while a matrix cell is a single bit. So the list carries a brutal per-edge overhead the matrix doesn't:

The list wins the sparse row by a landslide and loses the dense row just as badly. Setting the two costs equal gives the crossover exactly:

In plain words: once more than about 1 in 64 of all possible edges actually exists, a bit-matrix is not just faster for edge tests — it's genuinely smaller than the list, because it stops paying a fat pointer for every edge and starts paying one bit per pair. Below that line — where almost every real-world graph lives, since roads, friendships, and the web are overwhelmingly sparse — the list wins on both space and traversal speed, and it isn't close.

So the rule you can say out loud in an interview: adjacency list by default — it's what maps, social networks, and the web all use — and switch to a matrix only when the graph is dense, tiny, or your hot operation is "is there an edge?" answered a billion times.

The complete implementation

Here's the adjacency-list graph in full — the skeleton, the mirrored edge, the neighbour lookups, and the component-counting flood, assembled into one class:

package dev.fiveyear.graph;
 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
 
public final class Graph {
 
    private final int vertexCount;
    private final List<List<Integer>> adjacency;
 
    public Graph(int vertexCount) {
        this.vertexCount = vertexCount;
        this.adjacency = new ArrayList<>();
        for (int v = 0; v < vertexCount; v++) {
            adjacency.add(new ArrayList<>());
        }
    }
 
    /** Undirected edge: u knows v and v knows u. O(1). */
    public void addEdge(int u, int v) {
        adjacency.get(u).add(v);
        adjacency.get(v).add(u);
    }
 
    /** The vertices directly connected to u. */
    public List<Integer> neighbors(int u) {
        return adjacency.get(u);
    }
 
    /** How many edges touch u. O(1). */
    public int degree(int u) {
        return adjacency.get(u).size();
    }
 
    /** How many separate connected pieces the graph has. O(V + E). */
    public int connectedComponents() {
        boolean[] seen = new boolean[vertexCount];
        int components = 0;
        for (int start = 0; start < vertexCount; start++) {
            if (!seen[start]) {
                components++;
                bfs(start, seen);
            }
        }
        return components;
    }
 
    private void bfs(int start, boolean[] seen) {
        Queue<Integer> queue = new ArrayDeque<>();
        seen[start] = true;
        queue.add(start);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adjacency.get(u)) {
                if (!seen[v]) {
                    seen[v] = true;
                    queue.add(v);
                }
            }
        }
    }
}

And the matrix twin, for when the graph is dense:

package dev.fiveyear.graph;
 
import java.util.ArrayList;
import java.util.List;
 
public final class MatrixGraph {
 
    private final boolean[][] connected;
 
    public MatrixGraph(int vertexCount) {
        this.connected = new boolean[vertexCount][vertexCount];
    }
 
    /** Undirected → mirror the tick across the diagonal. O(1). */
    public void addEdge(int u, int v) {
        connected[u][v] = true;
        connected[v][u] = true;
    }
 
    /** Is there an edge between u and v? O(1). */
    public boolean hasEdge(int u, int v) {
        return connected[u][v];
    }
 
    /** u's neighbours — scans a whole row. O(V). */
    public List<Integer> neighbors(int u) {
        List<Integer> result = new ArrayList<>();
        for (int v = 0; v < connected.length; v++) {
            if (connected[u][v]) {
                result.add(v);
            }
        }
        return result;
    }
}

Here's our reunion, getting exactly the answers we drew by hand:

Graph g = new Graph(6);          // Ana=0 Ben=1 Cy=2 Dev=3 Eli=4 Fin=5
g.addEdge(0, 1);                 // Ana — Ben
g.addEdge(0, 2);                 // Ana — Cy
g.addEdge(1, 2);                 // Ben — Cy
g.addEdge(3, 4);                 // Dev — Eli
g.addEdge(4, 5);                 // Eli — Fin
 
g.degree(0);                     // 2   — Ana has two friends
g.neighbors(0);                  // [1, 2]   — Ben and Cy
g.connectedComponents();         // 2   — {Ana,Ben,Cy} and {Dev,Eli,Fin}
 
MatrixGraph m = new MatrixGraph(6);
m.addEdge(0, 1);
m.addEdge(0, 2);
m.hasEdge(0, 1);                 // true    — one array lookup
m.hasEdge(0, 3);                 // false
m.neighbors(0);                  // [1, 2]  — but this scanned a whole row

The interview corner

Graphs are the ultimate "it depends" topic, so the strongest thing you can do is ask before you code. Three questions settle almost everything:

• Directed or undirected? It decides whether addEdge mirrors, and whether the matrix is symmetric.
• Weighted or unweighted? Plain neighbours, or neighbours-with-a-cost? This is what later chooses BFS versus Dijkstra.
• How big, and how dense? V and E together pick your representation. And are the vertex ids a dense 0..n-1 range (use an array) or arbitrary keys like emails and UUIDs (use a map)?

The follow-up ladder

Interviewers rarely stop at "build a graph." They turn one dial at a time — so have a one-liner ready for each:

1. "The ids aren't 0..n-1 — they're emails." Swap the array-of-lists for a Map<String, List<String>>. Same O(V + E); you trade array indexing for hashing.
2. "Detect a cycle." Undirected: a DFS that meets an already-seen vertex which isn't its parent. Directed: a DFS that revisits a vertex still on the current recursion stack — a back edge.
3. "Order the tasks so every dependency comes first." Topological sort on a DAG — repeatedly peel off a vertex with no remaining prerequisites (Kahn's algorithm), or reverse a DFS post-order. Only defined if the graph is acyclic.
4. "Shortest path between two vertices." Unweighted → BFS in O(V + E). Non-negative weights → Dijkstra. Negative weights → Bellman–Ford.
5. "It's billions of edges — too big for one machine." Stop materializing it: stream edges, partition vertices across machines, or keep a compressed adjacency (CSR) / plain edge list. Rankings like PageRank then run as repeated passes over that stream, never a V × V grid.

Three mistakes that fail the round

• Adding an undirected edge only one way. Your adjacency goes asymmetric, traversals miss half the graph, and the component count inflates. Mirror every undirected edge — that one forgotten line is the Step 2 bug.
• Marking a vertex visited on dequeue instead of enqueue. The same vertex gets pushed by several neighbours and processed repeatedly. Mark it the instant it enters the queue.
• Traversing from one source and assuming you've seen everything. A single flood only fills one component. Loop over all vertices and start fresh from each unvisited one — or silently miss every other circle.

Where to go from here

You now own the foundation: vertices and edges, two ways to store them, and a flood that walks the connections. Everything else in graph-land is built on exactly this. Four natural next stops:

• BFS and DFS in depth — the two ways to flood a graph (a queue spreading level by level, a stack diving deep), and everything they unlock: shortest hops, cycle detection, topological order.
• Dijkstra's algorithm — that same flood, but with weighted roads, for real maps and networks.
• Union-Find (disjoint sets) — connected components in near-constant time per merge, and connectivity that updates live as new edges stream in.
• Minimum spanning trees and PageRank — the famous algorithms that ride on top of the representation you just built.

Next time an app tells you that you and a stranger share 12 mutual friends, you'll know there's no magic — just a set of dots, a set of lines, and a very old question about who's connected to whom.