Breadth-First Search
Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the current depth level before moving on to vertices at the next depth level, using a queue data structure to track which vertices to visit next. It is guaranteed to find the shortest path (in terms of number of edges) between a source vertex and any reachable vertex in an unweighted graph. BFS is widely used in network routing protocols, social network analysis, and solving puzzles like the shortest path in a maze.
Worked Example
Problem
Perform BFS on a graph with vertices {A, B, C, D, E} and edges {A-B, A-C, B-D, C-D, D-E}, starting from vertex A.
Solution
Step 1: Enqueue A, mark A visited. Queue: [A]. Step 2: Dequeue A, enqueue neighbours B and C. Queue: [B, C]. Visited: {A, B, C}. Step 3: Dequeue B, enqueue neighbour D (C already queued but not D). Queue: [C, D]. Visited: {A, B, C, D}. Step 4: Dequeue C, D already visited. Queue: [D]. Step 5: Dequeue D, enqueue E. Queue: [E]. Visited: {A, B, C, D, E}. Step 6: Dequeue E, no new neighbours. Queue: [].
Answer
BFS traversal order: A → B → C → D → E. Shortest path from A to E: A → B → D → E (3 edges).
BFS vs DFS Comparison
| Property | BFS | DFS |
|---|---|---|
| Data Structure | Queue (FIFO) | Stack (LIFO) or recursion |
| Traversal Order | Level by level | Branch by branch |
| Shortest Path (unweighted) | Guaranteed | Not guaranteed |
| Time Complexity | O(V + E) | O(V + E) |
| Space Complexity | O(V) | O(V) — call stack or explicit stack |
| Best Use Case | Shortest path, peer networks | Cycle detection, topological sort |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Algorithm
An algorithm is a finite, ordered sequence of well-defined instructions or rules designed to solve a specific problem or accomplish a task. Algorithms are fundamental to computer science because they provide a systematic approach to computation, independent of any particular programming language or hardware. They are evaluated on correctness, efficiency, and clarity, and form the basis of every software program ever written.
Binary Search
Binary search is a highly efficient search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half. At each step, it compares the target to the middle element and discards the half in which the target cannot lie. With a time complexity of O(log n), binary search is dramatically faster than linear search for large sorted datasets.
Big O Notation
Big O notation is a mathematical notation used to describe the upper bound of an algorithm's growth rate in terms of time or space, characterising its worst-case performance as the input size approaches infinity. It abstracts away constant factors and lower-order terms, focusing on the dominant factor that determines scalability. Big O is the industry standard language for comparing algorithm efficiency and is essential for technical interviews and software engineering.
The breadth-first search algorithm was first described by Konrad Zuse in his 1945 unpublished thesis on the programming language Plankalkül. It was later independently described by Edward F. Moore in 1959 in the context of finding the shortest path through a maze, and by C.Y. Lee in 1961 for circuit routing.