DataTerminology.comNEW
Also known as: BFS
Graph traversal that explores vertices by increasing distance from a source using a queue.
DESCRIPTION
Breadth-first search is a fundamental graph traversal algorithm that visits nodes level by level from a starting vertex. It naturally computes shortest paths in unweighted graphs, builds BFS trees, and finds connected components. BFS underpins algorithms in networking, web crawling, social network analysis, and AI pathfinding. It operates using a FIFO queue and a visited set to avoid revisiting nodes. BFS runs in linear time O(V+E) for adjacency-list representations.
ALTERNATIVE DEFINITIONS
Wikipedia
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures.
Concise description that applies to both trees and general graphs.
Princeton University (Algorithms, Sedgewick & Wayne)
Breadth-first search is a systematic exploration of the edges of a graph to discover every vertex that is reachable from s.
Emphasizes systematic edge exploration from a source vertex.
CP-Algorithms
Breadth First Search is one of the simplest algorithms for searching a graph and is the archetype for many important graph algorithms.
Highlights BFS as a foundational pattern for other graph algorithms.
RELATED TERMS
Graph Shortest Path Dijkstra’s Algorithm Queue Tree Traversal Connected Components Graph Traversal Level Order Traversal Adjacency List
COMPETING TERMS
RELATIONS
- Broader: Graph Traversal Search Tree Traversal
KNOWLEDGE AREAS
Mathematics AI Data Science Software Engineering
TARGET AUDIENCE
Data Scientist AI Engineer Software Developer Data Engineer MLOps Engineer Software Architect
EXTERNAL SOURCES
- Wikipedia - Breadth-first search
- NetworkX - Python BFS traversal API
- Princeton University - BFS theory and implementation notes
TOP QUESTIONS
When should I use Breadth-First Search over Depth-First Search?
Use BFS when you need shortest paths in unweighted graphs or level-order traversal. DFS is preferable for exploring deep structures or detecting cycles with less memory.
Category: Requirements
What is the time complexity of Breadth-First Search?
BFS runs in O(V+E) time on adjacency-list graphs, visiting each vertex and edge at most once.
Category: Example
How does Breadth-First Search find shortest paths?
Exploring by layers ensures the first time a vertex is discovered, the path length is minimal in unweighted graphs.
Category: Explanation
What data structures does Breadth-First Search use?
A FIFO queue to manage the frontier and a visited set or predecessor array to prevent revisits and reconstruct paths.
Category: Example
Can Breadth-First Search handle weighted graphs?
Plain BFS does not handle weights; use Dijkstra’s algorithm for nonnegative weights or 0-1 BFS for {0,1} weights.
Category: Alternatives
What is a common mistake when implementing Breadth-First Search?
Enqueuing the same node multiple times due to not marking visited upon discovery can degrade performance significantly.
Category: Mistakes
How is Breadth-First Search used in real-world systems?
It powers friend-of-a-friend queries, web crawlers, recommendation steps, and network reachability checks.
Category: Example
What is level-order traversal in relation to Breadth-First Search?
Level-order traversal of trees is a special case of BFS that visits nodes by depth from the root.
Category: Explanation
How does Breadth-First Search relate to connected components?
Repeated BFS from unvisited vertices identifies each connected component in an undirected graph.
Category: Example