BFS

Breadth-first search for shortest path in unweighted graphs.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

BFS Basics

BFS explores level by level using a queue. Visits all nodes at distance d before distance d+1. Guarantees shortest path in unweighted graphs.

Gobfs-traversal.go

24 linesLn 1, Col 1Go

Queue stores nodes to visit. Mark visited when enqueuing (not dequeuing) to avoid duplicates. Process neighbors, enqueue unvisited.

Track parent array to reconstruct path. Distance array gives shortest distance from start.

Gobfs-shortest-path.go

36 linesLn 1, Col 1Go

Parent array tracks BFS tree. Reconstruct by following parent from target to start. Reverse to get start→target path.

Start with multiple sources in queue. All sources distance 0. Propagates simultaneously. Distance to nearest source.

Gomulti-source-bfs.go

24 linesLn 1, Col 1Go

Initialize queue with all sources at distance 0. BFS naturally finds minimum distance to any source. Applications: rotting oranges, walls and gates.

For graphs with edge weights 0 or 1. Use deque: push 0-weight edges to front, 1-weight to back. Processes nodes in increasing distance order. O(V+E).

Go0-1-bfs.go

27 linesLn 1, Col 1Go

Deque maintains distance order. 0-weight edges processed immediately (front). 1-weight delayed (back). Faster than Dijkstra for 0-1 weights.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.