Every structure so far came with rules about who may connect to whom. A list node points to one successor. A tree node answers to exactly one parent, and cycles are forbidden. Now drop every rule and see what's left: a road atlas, a social network, the internet, and your project's dependency chart are all, structurally, the same object.

A graph is a network of connections, made up of points called vertices joined together by lines called edges. Each vertex can connect to any other vertex in the network, which makes graphs versatile for real-world problems like mapping roads between cities or modeling friendships on social media. Unlike trees, where connections flow in one direction from parent to child, graphs can have connections going any way between their vertices.

Graphs let us modify and analyze the connections in our network. Common tasks include adding new edges, removing connections, and finding paths between vertices. You might expect all of this to require some elaborate Graph class. In practice, a graph is usually just a hashmap from each vertex to a list of its neighbors, which is why adding a vertex or an edge below is a plain O(1) update, while anything that explores the network costs O(V + E), the price of actually walking it. The efficiency of these operations depends on how we store the graph and which algorithms we use:

Some graph algorithms use a mathematical concept called the Inverse Ackermann function, written as α(n). The math itself isn't important here. What matters is that the function grows so slowly that an O(α(n)) algorithm is practically as fast as an instant operation for any input you'll encounter.

Think of a graph like a map where vertices are locations and edges are the roads connecting them. Each vertex (or location) can store information, and it keeps track of all the other vertices it's directly connected to. Those are called adjacent vertices. Just like you can follow roads from one place to another, you can follow edges to trace a path through the graph.

Sometimes a path leads you back to where you started. That's called a cycle. In a social network, it would be like starting at one friend, walking through their connections, and eventually arriving back at the original friend through a chain of mutual friendships.

Adjacency lists are one way to represent a graph. Think of a contact list in your phone: each person (vertex) has their own list of friends (adjacent vertices). We build it with a hashmap, where the key is the person's name and the value is their list of friends. Finding all of someone's connections is just a hashmap lookup.

To build the list, we start with a list of edges: pairs of source and destination vertices. Each pair tells us that two vertices are connected, the same way you'd build a social network one friendship at a time. Once it's built, any vertex's neighbors are one lookup away.

An adjacency matrix is like a giant checklist showing who's connected to whom. Imagine a spreadsheet where both rows and columns list all the people (vertices), with a 1 in cells where two people are friends and 0 where they're not. Since every vertex needs a row and column to show every possible connection, the result is a square grid. Before scrolling on, estimate: how many cells does that grid need for 1,000 people who average 3 friends each?

A million. 1,000 rows times 1,000 columns, all to record about 3,000 friendships, so more than 99% of the cells hold zeros. Adjacency matrices are like using an entire phone book to store just a handful of phone numbers. They waste a lot of space because in real networks, each vertex only connects to a few others. Adjacency lists are usually the better choice: each person keeps their own contact list of just their friends, which saves both space and time.

Edges don't have to treat both endpoints equally. In undirected graphs, connections work both ways. Friendship on Facebook is a good example: if you're friends with someone, they're also friends with you. These two-way relationships are shown as simple lines between vertices.

Directed graphs (or digraphs) have one-way connections. Following someone on Twitter is a good example: you can follow them, but they might not follow you back. These one-way relationships are shown as arrows pointing from one vertex to another. The vertex where the arrow starts is called the source, and where it ends is the destination.

This difference in direction changes how we work with graphs. In undirected graphs, we can travel along any edge in either direction. In directed graphs, we can only follow the arrows in their specified direction. This matters when finding paths or checking whether two vertices are connected. Just because you can reach vertex B from vertex A doesn't mean you can get back to A from B in a directed graph.

Think of weighted graphs like a map where each road (edge) has extra information attached. Just like roads have distances, speed limits, or toll costs, weighted graphs assign values to their connections. These weights could represent anything measurable: miles between cities, minutes to travel, or dollars to spend.

Weighted graphs solve real-world problems like finding the shortest route between two locations or building the cheapest network of connections. The weights can be any number, even negative in some cases, and they change how you approach the problem entirely. Instead of finding any path between two points, you now need to consider the total weight of the path to find the optimal route.

Remember the binary tree rule that guaranteed traversals always finish? Graphs revoke it. A cycle in a graph is a circular path. You can start at any vertex, follow the connections, and eventually return to where you started. That's the same loop the chain of friendships traced earlier, now with a name. Cycles matter because they often represent dependencies in the graph, and because a traversal that ignores them will loop forever.

Cycles behave differently in directed and undirected graphs. In undirected graphs, cycles are easier to detect because we can move in any direction. In directed graphs, cycles are trickier because we have to follow the direction of the arrows. We often detect cycles in directed graphs using topological sorting, which fails the moment it hits a cycle since you can't order vertices that depend on each other in a loop.

One common way to find cycles is a depth-first search that tracks the nodes we're currently visiting. If we hit a node that's already on the current path, we've found a cycle. This is essential for task scheduling (where cycles cause deadlocks) and dependency management (where circular dependencies have to be caught early).

Graphs can model almost any kind of relationship, which is why they show up so often in coding interviews. Here are a few tips for solving graph problems well:

First, two checks from this page: why do adjacency lists beat matrices for most real networks, and how does a depth-first search recognize that it has found a cycle? If both come back quickly, you're ready. Graphs feel intimidating until you realize most problems boil down to "traverse the right nodes in the right order." Work through these to build intuition for representing graphs, detecting cycles, and applying the classic patterns that make hard problems collapse: