AlgoScope

Graph

Vertices joined by edges. The model for networks, maps and dependencies.

Data structures, data structure, beginnerAlso called undirected graph
Breadth-first search from vertex 0 with a queue.0012345
Breadth-first search from vertex 0 with a queue.0012345

BFS and DFS: Breadth-first from 0

Start, step 1 of 8

Breadth-first search from 0. A queue holds the frontier. Take the vertex that has waited longest, look at its neighbours, and enqueue the ones never seen before with their distance. Because of the queue, vertices come out in order of distance from the start.

Cost

Add vertex
O(1)
Add edge
O(1)
Neighbours
O(deg)
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.