Adjacency List
For each vertex, a list of its neighbours; compact for sparse graphs.
Decision · step 2 of 8BFS and DFS: Breadth-first from 0
Dequeue 0, distance 0. Its adjacency list: 1, 2. New: 1, 2, each at distance 1, enqueued.
What you will see
The same graph shown as picture and as per-vertex lists; a traversal walks one list at a time.
Cost
| edge lookup | O(deg u) |
|---|---|
| neighbours | O(deg u) |
| add edge | O(1) |
| Space | O(V + E) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Related
Taught by the same lesson
BFS and DFS covers these too, in the same run.