breadth-first search
A graph search that visits the start vertex, then all its neighbours, then all of theirs, spreading out in waves using a FIFO queue.
In more detail
Because vertices come off the queue in order of distance, the first time BFS reaches a vertex is along a path with the fewest edges. It runs in O(V + E) time. Recording each vertex's parent lets you rebuild the shortest path afterwards.
Example
The course uses it with collections.deque to walk a dependency graph and record how deep it goes.Related terms
- queue — A collection where items leave in the order they arrived: first in, first out, like a line at a shop counter.
- deque — A double-ended queue: a sequence that adds and removes items at either end in O(1) time; Python provides it as collections.deque.
- shortest path — The path between two vertices with the smallest total length: fewest edges in an unweighted graph, lowest total weight in a weighted one.
- frontier — The set of discovered but not yet processed vertices at the edge of a search, waiting in its queue, stack or heap.
- parent map — A dict recording, for each vertex a search reaches, the vertex it was reached from, so the path can be rebuilt afterwards.
- depth-first search — A graph search that follows one path as deep as it can go, then backs up to the last choice point and tries the next branch.
- dependency graph — The network of packages your project depends on, including what each of them depends on in turn.
Taught in
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers
- Dependency Risk And Typosquatting — Application Security & Threat Modeling for Engineers