Algorithms

BFS: Breadth-First Search

Цели урока

Understand the 'wave' traversal idea
Implement BFS with a queue
Find the shortest path in an unweighted graph
Know typical BFS applications

Предварительные знания

Queue
Graph representation

How does GPS find the path with the fewest turns? How do you find all friends of friends in a social network? How does a game AI find a path to a target? One algorithm solves all these problems - BFS.

Subway navigation
'People you may know' in LinkedIn
Pathfinding in games (for unweighted maps)
Web crawlers for search engines

Zuse, Moore, and Lee: BFS born from routing

BFS was invented more than once, independently. The first description, around 1945, came from Konrad Zuse in an unpublished thesis, where he used it to find the connected components of a graph, but the work sat in a drawer for decades. The canonical source is Edward F. Moore's 1959 paper The Shortest Path Through a Maze, presented at a switching-theory symposium at Harvard. Moore was solving a concrete engineering problem: find the shortest path through a maze, and his level-by-level wave expansion is BFS in its purest form. Almost immediately, in 1961, Chin Yang Lee at Bell Labs applied the same idea to routing wires on printed circuit boards and chips, and Lee's algorithm is still familiar to anyone who works on EDA tools. The notable part is that BFS came not from abstract graph theory but from practical problems: maze routing and wire layout. The FIFO queue, the shortest-path guarantee by edge count, and the O(V + E) cost were all there from the start.

Idea: Waves from the Source

**Consider a stone thrown into water.** Waves spread in circles: first the nearest points, then the distant ones. BFS works the same way - first all neighbors, then neighbors of neighbors.

**The key structure is a queue (Queue).** FIFO guarantees that we process everyone at distance k before distance k+1.

**BFS = Queue, DFS = Stack (or recursion).** Remember this forever.

If BFS starts from vertex A and finds B on iteration 3, what does that mean?

BFS Implementation

**Important:** we add to visited WHEN ADDING to the queue, not when popping. Otherwise a vertex can end up in the queue multiple times.

Operation	Complexity	Why
Time	O(V + E)	Each vertex and edge visited once
Memory	O(V)	visited + queue hold at most V vertices

**Use deque, not list!** `list.pop(0)` is O(n), while `deque.popleft()` is O(1).

Why should visited.add() happen BEFORE queue.append(), not after queue.popleft()?

Shortest Path (Unweighted)

BFS automatically finds the **shortest path by number of edges**. We just need to remember where we came from.

**Distances to all vertices:**

**Subway navigation** uses exactly BFS - all stations are equal, what matters is the number of transfers.

BFS found the path A→B→C→D. Can there be a shorter path A→D?

Applications of BFS

**Classic BFS problems:**

**Social networks:** degrees of separation (6 handshakes)
**Games:** NPC pathfinding, flood fill
**Web crawlers:** traversing pages level by level
**Compilers:** garbage collection (mark phase)

For which task is BFS NOT suitable?