What you'll learn
A graph is the most general structure: a set of vertices connected by edges. Roads, social networks, web links, dependencies, circuits — almost any relationship is a graph. First we need to know how to store one.
By the end you'll be able to:
- Use graph vocabulary: vertex, edge, directed, weighted, degree
- Store a graph as an adjacency matrix or an adjacency list
- Choose the right representation for a given graph
Vertices & edges
A graph is G = (V, E): a set of vertices V and edges E connecting them. Here's the graph we'll represent two ways below:
Directed & weighted
| Kind | Meaning | Example |
|---|---|---|
Undirected | Edges go both ways | Facebook friendship |
Directed | Edges have a direction (u → v) | Twitter following, web links |
Weighted | Edges carry a cost/distance | Road maps, network latency |
Cyclic / Acyclic | Has a cycle / has none (a DAG) | Dependencies must be acyclic |
Adjacency matrix
An n × n grid where matrix[u][v] = 1 when an edge exists. Checking "is there an edge u–v?" is O(1), but it always uses O(n²) space — wasteful for sparse graphs:
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 | 0 | 0 |
| B | 1 | 0 | 1 | 0 | 1 | 0 |
| C | 0 | 1 | 0 | 0 | 0 | 1 |
| D | 1 | 0 | 0 | 0 | 1 | 0 |
| E | 0 | 1 | 0 | 1 | 0 | 1 |
| F | 0 | 0 | 1 | 0 | 1 | 0 |
Adjacency list
Each vertex stores a list of its neighbors. It uses only O(V + E) space and makes "iterate a vertex's neighbors" fast — the right choice for most (sparse) real-world graphs:
In code
# adjacency list — a dict mapping each vertex to its neighbors
graph = {
"A": ["B", "D"],
"B": ["A", "C", "E"],
"C": ["B", "F"],
"D": ["A", "E"],
"E": ["B", "D", "F"],
"F": ["C", "E"],
}
print(graph["B"]) # neighbors of B, in O(1)
# adjacency matrix — n x n grid, 1 if an edge exists
n = 6
matrix = [[0] * n for _ in range(n)]
matrix[0][1] = matrix[1][0] = 1 # undirected edge A-B| Adjacency matrix | Adjacency list | |
|---|---|---|
Space | O(V²) | O(V + E) |
Edge exists? | O(1) | O(degree) |
Iterate neighbors | O(V) | O(degree) |
Best for | Dense graphs | Sparse graphs (most real ones) |
Recap & quick check
Key takeaways
- A graph is vertices (V) connected by edges (E); edges may be directed and/or weighted.
- An adjacency matrix is an n×n grid: O(1) edge checks but O(V²) space.
- An adjacency list stores each vertex's neighbors: O(V+E) space, fast neighbor iteration.
- Use a list for sparse graphs (most real ones), a matrix for dense graphs.
- A DAG is a directed graph with no cycles — key for scheduling (Module 25).
Quick check
1. What does an adjacency matrix store?
2. For a sparse graph, which representation is more space-efficient?
3. Checking whether edge u–v exists is O(1) in:
4. A directed graph with no cycles is called:
Now that we can store a graph, let's explore one. Next up: Module 24 — Graph Traversal: BFS & DFS.