AlgoScope

Adjacency List

For each vertex, a list of its neighbours. Compact for sparse graphs.

Data structures, data structure, beginner
Vertex 0 is dequeued at distance 0. New neighbours 1, 2 are enqueued.001121345u
Vertex 0 is dequeued at distance 0. New neighbours 1, 2 are enqueued.001121345u

BFS and DFS: Breadth-first from 0

Decision, step 2 of 8

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)

Leads to

Topics that need this one first.

Taught by the same lesson

BFS and DFS covers these too, in the same run.