Adjacency List
For each vertex, a list of its neighbours. Compact for sparse graphs.
BFS and DFS: Breadth-first from 0
Dequeue 0, distance 0. Its adjacency list: 1, 2. New: 1, 2, each at distance 1, enqueued.
Cost
- Edge lookup
- O(deg u)
- Neighbours
- O(deg u)
- Add edge
- O(1)
- Space
- O(V + E)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
BFS and DFS covers these too, in the same run.