The Graph
A graph is a set of vertices and a set of edges that record relationships between them. Stations and track, people and friendships, pages and links, courses and prerequisites — anything made of things plus connections between things is a graph. It is also the most general structure in this book: the linked list, the tree, and the grid from the earlier chapters are all special cases of it.
Why graphs: things, and the connections between them
When relationships stop being one-to-one or one-to-many, and start being many-to-many with loops, you need a graph.
Look back at the structures so far. An array is one row. A linked list is one chain. A tree branches downward and never returns. They all share one limit: real relationships are often many-to-many, and they can loop back.
Here are four everyday examples that none of the earlier structures can hold:
Each station is a vertex and each stretch of track is an edge. An interchange station joins several lines, and you can ride in a loop back to where you started. Branches plus loops: a tree cannot draw this.
Each person is a vertex. “Is a friend of” is an undirected edge; “follows” is a directed one. A friend of a friend of A can be A again, so the relationships form a web, not a tree that only goes down.
Each course is a vertex and “is a prerequisite of” is a directed edge. Data structures needs arrays first; operating systems needs C first. All these “this must come before that” rules form a directed graph.
Each page is a vertex and each hyperlink is a directed edge. Google started by treating the whole web as one huge graph and ranking results by how pages link to each other (PageRank).
Graphs come with a small vocabulary. Each word names something simple. The picture below labels all of them at once:
| Term | In plain words | Notation |
|---|---|---|
| Vertex (V) | A point in the graph; it holds the data | node / vertex; the count is written |V| or n |
| Edge (E) | A link between two vertices; it records one relationship | edge; the count is written |E| or m |
| Directed / undirected | Does the edge have an arrow? Following is directed; shaking hands is not | directed / undirected |
| Weighted | The edge carries a number: distance, time, or cost | weight w(u, v) |
| Degree | How many edges meet at this vertex | In a directed graph it splits into in-degree (arrows in) and out-degree (arrows out) |
| Path | A sequence of vertices you walk through along edges | path; its length is the number of edges, or the sum of the weights |
| Cycle | Leaving a vertex and coming back to it along edges | cycle; a directed graph with no cycle is a DAG |
| Connected | Every pair of vertices has a path between them | a connected component is a group of vertices that can all reach each other |
Three variations, drawn side by side:
An edge has no direction, so the relationship is symmetric: A and B are friends of each other, and a train line runs both ways. A tree is a graph of this kind: undirected, connected, and with no cycle.
An edge has an arrow, so the relationship runs one way: A follows B is not the same as B follows A, and page A links to page B. Degree now splits into in-degree (arrows coming in) and out-degree (arrows going out). A singly linked list is a directed graph with one outgoing edge per node.
Each edge carries a number, its weight: a distance, a duration, a cost. A shortest path question then asks for the smallest total weight, not the fewest edges. Weight and direction are independent choices. The graph drawn here happens to be directed and weighted at the same time, but a weighted undirected graph is just as common.
The point: the earlier structures are all graphs
This is the one sentence to take away from the chapter. A singly linked list is a graph where every vertex has one outgoing edge, laid out in a line. A tree is a graph that is connected, has no cycle, and has one vertex chosen as the root. A grid is a graph where each cell is a vertex and cells that touch up, down, left, or right are joined by an edge. You have been working with graphs all along. This chapter takes the most general form and studies it directly.
A bridge problem that started a field
In 1736 Leonhard Euler studied the seven bridges of Konigsberg: can you cross all seven bridges, each exactly once, in a single walk? He replaced each piece of land with a vertex and each bridge with an edge, and proved it is impossible. That is where graph theory begins. The same abstraction now supports navigation, social networks, compilers, chip routing, and the internet itself. Turning a complicated situation into vertices and edges is one of the most useful moves in computer science.
In memory: adjacency matrix and adjacency list
A graph has no natural memory layout, so you choose how to record which vertices are joined.
An array has contiguous memory and an index formula. A tree has a node with two references. A graph has neither, because its shape varies. Two representations cover almost all practical use, and choosing between them is a plain time against space trade-off. Click a vertex below and compare the same graph in both forms:
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 1 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 | 0 | 1 |
| 4 | 0 | 0 | 0 | 1 | 0 |
A V x V table where matrix[i][j] = 1 means there is an edge from i to j (a weighted graph stores the weight instead). For an undirected graph the table is symmetric across the diagonal. Advantage: asking whether i and j are joined takes one read, O(1). Cost: it occupies O(n²) space however few edges exist.
Each vertex keeps a list of its neighbors (an array of arrays, or a hash map of arrays). Only the edges that exist are stored, so the space is O(V + E), and reading all neighbors of a vertex is direct. Cost: asking whether i and j are joined means scanning i’s list, O(deg i) in the worst case. This is the default for problem solving and for most production code.
| Compared on | Adjacency matrix | Adjacency list |
|---|---|---|
| Space | O(V²) always | O(V + E) grows with the edges |
| Is there an edge u–v? | O(1) — read matrix[u][v] | O(deg u) — scan the neighbors of u |
| Visit all neighbors of u | O(V) — scan the whole row, including the zeros | O(deg u) — one step per neighbor |
| Add one edge | O(1) | O(1) |
| Fits | Dense graphs (E close to V²), and repeated edge tests | Sparse graphs (E much smaller than V²), and frequent neighbor traversal ← the default |
A third form: the edge list
The simplest form of all: one array whose elements are edges, [u, v, w]. It suits algorithms that read all edges once and then sort them, such as Kruskal’s minimum spanning tree, or cycle detection with union-find. But listing the neighbors of one vertex means scanning every edge, which is too slow for traversal. So an edge list is usually only the input format: the problem hands you an edge list, and your first step is to turn it into an adjacency list.
The core: two ways to walk a graph, BFS and DFS
★ Core of the chapterThere are two ways to reach every vertex: spread outward layer by layer (BFS), or follow one path to the end (DFS).
Most graph algorithms are built on one operation: visit every vertex. Two ways to do that have become standard, and each reuses a structure you already know.
The search spreads outward one layer at a time: visit the start, then all of its neighbors, then their unvisited neighbors, and so on. It is driven by a queue (first in, first out). Vertices come out grouped by how many edges they are from the start, which is why BFS finds the fewest-edges path in an unweighted graph.
The search follows one path as far as it goes, then backs up to the last junction and tries another. It is driven by a stack (or by recursion, where the call stack is that stack). It suits problems about exploring all paths, connected components, and cycles.
The clearest way to see the difference is to watch it. The graph below has 8 vertices. Switch between BFS and DFS and step through it. Watch how the queue or stack changes, how the visited set grows, and in what order the vertices light up (the #number under each vertex is its visit order).
Why graph traversal always needs a visited set
This is the real difference between a graph and a tree. A tree has no cycle: walking down from the root never returns to an ancestor, so tree traversal (chapter 7) needs no visited set. A graph can have a cycle: A to B to C back to A. Without a record of which vertices have been reached, the traversal goes around that cycle forever and the program never stops. So the rule is: check visited before entering a vertex, and mark it immediately. In BFS, mark a vertex when you put it in the queue, not when you take it out — otherwise every edge pointing at that vertex queues it again.
| BFS, breadth-first | DFS, depth-first | |
|---|---|---|
| Helper structure | Queue (FIFO) | Stack or recursion (LIFO) |
| Visit order | By layer, nearest first | One path to the end, then back up |
| Time | Both O(V + E) with an adjacency list — each vertex is handled once, each edge is looked at once | |
| Space | O(V) — the visited set, plus a queue that at worst holds the widest layer | O(V) — the visited set, plus a stack that at worst equals the longest path |
| Best at | Shortest path in an unweighted graph, spreading by layer (rotting oranges) | Connected components and islands, cycles, topological order, backtracking |
Remember this complexity: O(V + E)
With an adjacency list, both BFS and DFS run in O(V + E). Each vertex is processed once, which contributes V. Each edge is examined once in a directed graph, or once from each endpoint in an undirected graph, which contributes E. This is the most basic complexity in graph theory, and almost every later algorithm grows out of it. With an adjacency matrix the same traversal costs O(V²) instead, because finding the neighbors of a vertex means scanning a whole row.
Build it: adjacency list, BFS, DFS
The animations from §03, written as code you can run. These templates are the skeleton of most graph problems.
A problem usually hands you an edge list, for example edges = [[0,1],[0,2],...]. The first step is almost always to turn it into an adjacency list, and then BFS or DFS follows the template. Start with building the graph and running BFS. The highlighted lines are the ones that matter: a vertex is marked at the moment it enters the queue.
collections.deque for the queue, because its popleft() is O(1). Never use list.pop(0): it is O(n) and turns the whole BFS into O(V · E).DFS has two forms: recursive, which is short and direct but can exhaust the call stack on a deep graph, and iterative, which uses an explicit stack and is safe. Learn both.
RecursionError. Either raise it with setrecursionlimit, or write the iterative version.The last piece: a grid as a graph. A matrix (chapter 1) is already a graph. Each cell (r, c) is a vertex, and it is joined by an edge to the cell above, below, left, and right. That is why flood fill and shortest path in a maze are graph problems. You do not build an adjacency list for it; a direction array covers the four neighbors in one loop. This is the standard grid template:
Two variations on the direction array
(1) Eight directions, including the diagonals: write 8 offsets in dirs. (2) Writing a new value into the grid (1 becomes 2, or 0) removes the need for a separate visited matrix, but it destroys the input. In an interview, ask first whether you are allowed to modify the given array. Grid BFS works the same way: replace the stack with a queue.
Three languages: no built-in graph type, but a standard way to write one
No language ships a Graph class. Everyone builds an adjacency list from an array or a hash map, with different containers.
Unlike arrays and hash maps, none of the three languages has a ready-made graph type. But the way an adjacency list is written is nearly the same everywhere; only the container differs. Remember each language’s way of building the list and what it uses for visited, and any graph problem becomes routine.
defaultdict(list) is the standard way to build a graph in Python: it removes the “initialize the key first” boilerplate. For a weighted graph, store (neighbor, weight) tuples in the same structure.| Need | Java | Python | JavaScript |
|---|---|---|---|
| Adjacency list (integer vertices) | List<List<Integer>> | defaultdict(list) | Array.from(..., () => []) |
| Adjacency list (any vertex type) | Map<T, List<T>> | defaultdict(list) | Map<T, T[]> |
| Queue (BFS) | ArrayDeque | collections.deque | array plus a read index head |
| Stack (iterative DFS) | ArrayDeque | list (append/pop) | Array (push/pop) |
| visited (integer vertices) | boolean[] | [False]*n or set | new Array(n).fill(false) |
| Min-heap (Dijkstra) | PriorityQueue | heapq | none built in; write one or use a library |
JavaScript has no built-in heap
This is the main gap when solving graph problems in JavaScript: there is no priority queue or heap. For Dijkstra you either write a binary heap yourself (chapter 9), or use the O(V²) version that scans for the smallest distance each round, which is fine on a small graph. If you interview in JavaScript, have a heap implementation ready.
Three patterns: grids, topological order, shortest paths
★ Interview coreGraph problems are many, but the frequent ones fall into three groups. Each gets one classic problem, taken apart frame by frame.
A grid is a graph
A large group of medium LeetCode problems is really DFS or BFS on a grid: number of islands, max area of island, surrounded regions, rotting oranges. They share one mapping: each cell is a vertex, and cells that touch up, down, left, or right are joined by an edge. Then you traverse. The main technique is called sinking or coloring: write a new value into a cell as you visit it, so the value doubles as the visited set and nothing is counted twice.
LC 200 · Number of Islands
MEDIUMProblem: given a grid of '1' (land) and '0' (water), count the islands. Land cells that touch up, down, left, or right belong to the same island. Idea: scan cell by cell. When you meet a '1' that has not been sunk, add 1 to the island count, then run DFS from there and turn every connected '1' into '0'. That way the same island is never counted again. In the animation, green means sunk, already counted as part of some island.
Complexity and follow-up questions
Time is O(rows x cols): each cell is entered at most once, because sinking turns it into 0. The space is the recursion stack, at worst O(rows x cols) when the whole grid is land. Common follow-ups: “what if you may not modify the grid?” (keep a separate visited matrix), “what if the recursion overflows?” (switch to BFS or iterative DFS), and “what if you need the largest island area?” (LC 695, let DFS return the number of cells it sank). Sinking is the template for every connected-component problem on a grid.
Topological sort: ordering tasks that depend on each other
Course planning, build dependencies, task scheduling — all of these ask the same question: given a set of tasks with “this must come before that” constraints, is there a valid order? That order is a topological sort. It exists only for a directed acyclic graph (DAG). As soon as there is a cycle — A depends on B and B depends on A — neither can go first, and no order exists.
The most direct algorithm is Kahn’s algorithm, which works the way course registration does:
The in-degree of a vertex is the number of arrows pointing at it, that is, how many prerequisites it still has.
Every course with no prerequisite left (in-degree 0) can be taken now, so put all of them in the queue.
Dequeue a course (it is finished) and subtract 1 from the in-degree of each course it points at. Any that reaches 0 enters the queue. Repeat until the queue is empty.
LC 207 · Course Schedule
MEDIUMProblem: there are numCourses courses, and prerequisites[i] = [a, b] means you must take b before a. Decide whether you can finish all of them. Idea: this is asking whether the directed graph has a cycle. If a full topological sort completes, there is no cycle. Step through Kahn’s algorithm below and watch the in-degree under each vertex fall to 0 as courses leave the queue.
Cycle detection: directed and undirected need different methods
For a directed graph there are two correct methods. (1) Topological sort, as in this problem: if fewer vertices leave the queue than the graph holds, there is a cycle. (2) DFS with three states — unvisited, on the current recursion stack, finished. Reaching a finished vertex is fine, because that path was already explored; reaching a vertex that is still on the current stack is a cycle. For an undirected graph, neither applies directly: use union-find, or run DFS while ignoring the edge you just came from, otherwise the traversal sees the parent again and reports a cycle that is not there. Follow-up: LC 210 asks for the actual topological order, which is just the dequeue order recorded as you go. Complexity O(V + E).
Shortest paths: the cheapest way from A to B
Before choosing an algorithm, settle one question: do the edges carry weights? The answer decides the tool.
When every edge costs the same, BFS spreads by layer, so the layer at which a vertex is first reached is the fewest number of steps to it. No advanced algorithm is needed; a queue is enough. This is the first choice for “fewest steps” and “fewest operations” questions.
When edges carry different weights (distance, duration), BFS no longer works: a path with fewer edges can have a larger total. Use Dijkstra. A min-heap returns the vertex that is currently nearest and not settled yet; you settle it, then relax its neighbors. It needs every weight to be non-negative, and it reuses the heap from chapter 9.
Now look at Dijkstra in detail. Its rule is: among the vertices that are not settled, take the one with the smallest dist; its shortest distance can be fixed right now. That holds because no weight is negative, so any longer detour only costs more and can never overtake. After settling a vertex, use it to relax its neighbors: if dist[u] + w < dist[v]: update dist[v]. Step through the 5-vertex example and watch how each dist is lowered.
| node | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| dist | 0 | ∞ | ∞ | ∞ | ∞ |
LC 743 · Network Delay Time
MEDIUMProblem: a signal is sent from node k. times[i] = [u, v, w] means the signal takes w time to travel from u to v. Find the time it takes to reach all n nodes, or -1 if some node is unreachable. Idea: this is a plain single-source shortest path. Run Dijkstra from k to get the shortest time to every node. The answer is the largest of those times, because the last node to receive the signal decides the total. If any node is still infinity, it is unreachable, so return -1.
heapq is a min-heap, so putting the distance first in the tuple makes it pop in distance order. max(dist[1:]) at the end skips index 0, because the nodes are numbered from 1.Three questions people ask about Dijkstra
(1) Why a min-heap? So that taking the nearest unsettled vertex costs O(log V) instead of a linear scan. (2) Why do negative weights break it? Dijkstra fixes a vertex’s distance the moment it leaves the heap and never revisits that decision. That is only sound when no weight is negative, because a detour can then only cost more. With a negative edge, a path found later can be cheaper, so a vertex gets settled too early and the answer is wrong. Use Bellman-Ford instead, at O(V · E); it also detects a negative cycle. (3) What is the complexity? With a binary heap it is O((V + E) log V), which is often written O(E log V) when the graph is connected and E is at least V - 1.
Do not confuse BFS with Dijkstra
For a shortest path in an unweighted graph, or one where all weights are equal, do not reach for Dijkstra — BFS is simpler and faster. Dijkstra is the upgrade you need only when the weights differ and are non-negative. When a problem says “fewest steps” or “fewest operations”, think BFS first. When it says “shortest distance” or “smallest cost” with varying edge weights, think Dijkstra.
Problem set: 9 graph problems
SelectedGrid DFS/BFS, multi-source BFS, topological sort, shortest paths, and implicit graphs. Easy to hard; your checkmarks are stored locally.
Quiz
✎ QuizAnswer all 8 correctly to mark this chapter complete.
A graph has 1,000,000 vertices, but each vertex has about 3 edges on average. Which representation should you use?
Why must BFS use a queue instead of a stack?
What happens if you traverse a graph that contains a cycle and forget to keep a visited set?
Why does a binary tree traversal not need a visited set, while a graph traversal does?
Which statements about topological sort are correct? (Select all that apply.)
Which method correctly decides whether a directed graph contains a cycle?
In a graph where every edge has weight 1 (or has no weight), which algorithm best finds the shortest path from a start vertex to every other vertex? (Write the algorithm name.)
Why can Dijkstra's algorithm not be used on a graph with a negative edge weight?
- A graph is vertices plus edges. The linked list, the tree, and the grid are all special cases: a singly linked list is a graph with one outgoing edge per vertex laid out in a line, a tree is connected with no cycle, and a grid joins each cell to the cells above, below, left, and right.
- Two representations: an adjacency matrix uses O(V²) space and tests an edge in O(1); an adjacency list uses O(V + E) space and scans neighbors quickly. Use an adjacency list for a sparse graph, which is almost every problem you will meet.
- Two traversals: BFS uses a queue and spreads by distance from the start; DFS uses a stack or recursion and goes deep first. Both are O(V + E) with an adjacency list. A graph can have a cycle, so the visited set is required, and in BFS you mark a vertex when you enqueue it, not when you dequeue it.
- Grid problems are DFS or BFS on a grid plus a direction array
dirs. Sinking or coloring writes a new value into each visited cell, which serves as the visited set (LC 200 is the template). - Topological sort exists only for a directed acyclic graph. Kahn’s algorithm enqueues in-degree 0, then decreases the in-degree of each successor on dequeue. Vertices left over means a cycle — one of the two standard cycle tests for a directed graph; the other is DFS with three states. Undirected graphs need a different method.
- Shortest paths depend on the weights. Unweighted: use BFS, where the layer number is the fewest edges. Non-negative weights: use Dijkstra (greedy plus a min-heap, O((V + E) log V)). A negative weight breaks Dijkstra, because a settled vertex is never reconsidered; use Bellman-Ford at O(V · E) instead.