Graph Fundamentals
Graph vocabulary, the three standard representations and their costs, and how to model problems as graphs.
What you will learn
Graph vocabulary, the three standard representations and their costs, and how to model problems as graphs.
Prerequisites: Modules 9 (queues) and 11 (trees).
Vocabulary
Vertex, edge, directed/undirected, weighted/unweighted, simple graph, multigraph, degree, indegree/outdegree, path, cycle, connected component, DAG, bipartite graph, tree, and spanning tree.
Representations
Adjacency matrix: O(V²) memory.
Adjacency list: O(V+E) memory.
Implicit graphs (states are nodes, transitions are edges).
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2): Is (u, v) an edge?
Iterate neighbours of u dense graphs, Floyd–Warshall sparse graphs (most real graphs)
The handshake lemma — the degrees sum to 2E — holds because every undirected edge contributes to two degrees.
#include <bits/stdc++.h>
using namespace std;
int main() {
int V = 5;
vector<tuple<int, int, int>> edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {3, 4, 3}}; // u, v, weight
vector<vector<int>> matrix(V, vector<int>(V, 0));
vector<vector<pair<int, int>>> adj(V);
for (auto [u, v, w] : edges) { // undirected: store both directions
matrix[u][v] = matrix[v][u] = w;
adj[u].push_back({v, w}); adj[v].push_back({u, w});
}
cout << "adjacency matrix:\n";
for (auto& row : matrix) { for (int x : row) cout << setw(3) << x; cout << '\n'; }
cout << "adjacency list:\n";
for (int u = 0; u < V; ++u) { cout << u << ":"; for (auto [v, w] : adj[u]) cout << " " << v << "(w" << w << ")"; cout << " degree " << adj[u].size() << '\n'; }
int degreeSum = 0; for (auto& l : adj) degreeSum += (int)l.size();
cout << "sum of degrees = " << degreeSum << " = 2 * E = " << 2 * edges.size() << '\n';
cout << "memory for V = 100000 sparse graph with E = 200000: matrix " << 100000LL * 100000 << " cells vs list " << 100000 + 2 * 200000 << " entries\n";
}adjacency matrix:
0 4 1 0 0
4 0 2 1 0
1 2 0 5 0
0 1 5 0 3
0 0 0 3 0
adjacency list:
0: 1(w4) 2(w1) degree 2
1: 0(w4) 2(w2) 3(w1) degree 3
2: 0(w1) 1(w2) 3(w5) degree 3
3: 1(w1) 2(w5) 4(w3) degree 3
4: 3(w3) degree 1
sum of degrees = 12 = 2 * E = 12
memory for V = 100000 sparse graph with E = 200000: matrix 10000000000 cells vs list 500000 entriesGraph input and modeling
Index conversion, multiple edges, self-loops, disconnected graphs, zero-weight edges, and large sparse graphs.
Inputs are often 1-indexed; convert once on reading (u − 1) and never mix conventions.
Decide whether parallel edges and self-loops are allowed; they break some algorithms (bridge finding must treat parallel edges specially, Module 33).
Always loop over all vertices when starting traversals — a graph may be disconnected.
Implicit graphs: a word ladder, a sliding puzzle or a grid with keys is a graph whose vertices are *states*; generate neighbours on demand instead of storing edges (Module 35).
Quiz
? Which representation suits a road network with 10⁶ junctions and 3·10⁶ roads?
+ Adjacency list :: O(V + E) memory; a matrix would need 10¹² cells.
- Adjacency matrix :: Far too much memory.
- Edge list only :: Neighbour iteration would be slow.
- A tree :: Roads form cycles.
? The degrees of an undirected graph sum to…
+ 2E :: Each edge counts at both endpoints.
- E :: Each edge has two endpoints.
- V :: No.
- V + E :: No.
? Which are implicit graphs? (select all that apply)
+ Sliding-puzzle board states with moves as edges :: Generated on demand.
+ Words differing by one letter :: Word ladder.
- A list of roads read from a file :: That is explicit.
+ Grid cells with keys collected :: State = (row, col, keys).