Foundations
Graph theory foundations
Vertices, edges, degrees, paths and cycles; BFS/DFS complexity from adjacency.
Question: is BFS right for a graph with 10⁵ vertices and 2·10⁵ edges?
With an adjacency list, yes: O(V + E) = 3·10⁵. With an adjacency matrix, you die: O(V²) = 10¹⁰. This page unpacks why each representation has the cost it has, and why the degree-sum rule gives you V + E.
By the numbers: representation comparison
| Representation | BFS/DFS | Single-neighbor query | Memory |
|---|---|---|---|
| Adjacency list | O(V + E) | O(degree) | O(V + E) |
| Adjacency matrix | O(V²) | O(1) | O(V²) |
Sparse graph (E ~V): adjacency list much faster. Dense graph (E ~V²): matrix ties. Interviews are almost always sparse → adjacency list.
Where it comes from
The degree-sum rule
Every edge contributes to two vertices, so Σ degree(v) = 2E. BFS/DFS visits each vertex once and each edge once (undirected) or twice (directed) → total V + E.
BFS layer cost
BFS advances level-by-level with a queue. At each level, you walk the neighbors of all vertices at that level. Total edges walked = E (each edge once), total vertices = V. Memory: queue worst case O(V). That's why shortest path (unweighted, undirected) is BFS at cost O(V + E).
Tree = connected acyclic graph
n vertices, n-1 edges, exactly one path between any pair. On a tree BFS/DFS is still O(V + E) = O(n) (E = n-1). Tree DFS (LC 100, 104, 110) and the tree patterns are the special case of this family.
Trap: "a matrix is always faster because O(1) neighbor query"
Wrong direction: O(1) is for a single (u,v) pair. But BFS asks for all neighbors of a vertex; in a matrix that's V cells. If degree(u) is small (sparse graph) the adjacency list is far faster, because you only walk real neighbors. At 10⁵ vertices the matrix checks 10¹⁰ cells per BFS, while the list walks 2·10⁵ edges.
Where to go next
- graph-dfs pattern - where DFS is used in DSA.
- grid-graph-bfs pattern - BFS on a grid.
- tree-dfs pattern - a tree is an acyclic graph.
- LC 200 Number of Islands - grid-graph BFS/DFS.
- LC 207 Course Schedule - directed graph + cycle detection.
- LC 261 Graph Valid Tree - tree = n-1 edges + connected.
Exercise
Click the graph on the right and add a few edges. Watch each vertex's degree rise as edges attach. Now sum the degrees: is it 2 × edge count? That's the Σ degree = 2E rule made concrete.
Add edge: -
Degree