Introduction to Breadth-First Search
What is Breadth-First Search?
Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices of a graph at the present depth before moving on to vertices at the next depth level.
In simpler terms, BFS explores a graph layer by layer, visiting all neighbors of a vertex before moving on to their neighbors.
Key Characteristics
- Queue-Based: Uses a queue data structure to keep track of vertices to visit
- Level by Level: Explores all vertices at the current level before moving to the next level
- Shortest Path: Guarantees the shortest path in unweighted graphs
- Complete: Will find a solution if one exists in a finite graph
- Memory Intensive: Requires more memory than depth-first search
How BFS Works
- Start at a source vertex and mark it as visited
- Enqueue the source vertex into a queue
- While the queue is not empty:
- Dequeue a vertex from the queue
- Process the vertex (e.g., print it)
- Enqueue all unvisited neighbors of the vertex and mark them as visited
Basic BFS Implementation
Here's a simple implementation of BFS for a graph represented as an adjacency list:
Time and Space Complexity
Time Complexity:
O(V + E), where V is the number of vertices and E is the number of edges in the graph.
We visit each vertex once and each edge once.
Space Complexity:
O(V), where V is the number of vertices in the graph.
In the worst case, the queue might contain all vertices of the graph.
Applications of BFS
- Shortest Path: Finding the shortest path between two vertices in an unweighted graph
- Connected Components: Finding all connected components in an undirected graph
- Level Order Traversal: Traversing a tree level by level
- Bipartite Graph: Checking if a graph is bipartite
- Web Crawling: Crawling web pages and their links
- Social Networks: Finding all friends within a certain degree of separation
Learning Objective
Understand the fundamental concepts of breadth-first search and its importance in graph traversal and shortest path problems.
What is Breadth-First Search?
Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices of a graph at the present depth before moving on to vertices at the next depth level.
In simpler terms, BFS explores a graph layer by layer, visiting all neighbors of a vertex before moving on to their neighbors.
Think of BFS as exploring a maze by first checking all paths that are one step away, then all paths that are two steps away, and so on, until you find the exit.
Key Characteristics
Queue-Based
Uses a queue data structure (FIFO - First In, First Out) to keep track of vertices to visit next.
Level by Level
Explores all vertices at the current level before moving to the next level, creating a breadth-wise expansion.
Shortest Path
Guarantees the shortest path in unweighted graphs, as it always finds the path with the fewest edges first.
Memory Intensive
Requires more memory than depth-first search because it needs to store all vertices of the current level.
How BFS Works
1Start
Begin at a source vertex, mark it as visited, and enqueue it into a queue.
2Dequeue
Remove the front vertex from the queue and process it (e.g., print it or add to result).
3Explore
Examine all unvisited neighbors of the current vertex.
4Enqueue
Mark each unvisited neighbor as visited and enqueue them into the queue.
5Repeat
Continue steps 2-4 until the queue is empty, meaning all reachable vertices have been visited.
Basic BFS Implementation
Here's a simple implementation of BFS for a graph represented as an adjacency list:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748function bfs(graph, startVertex) { // Set to keep track of visited vertices const visited = new Set(); // Queue for BFS const queue = []; // Mark the start vertex as visited and enqueue it visited.add(startVertex); queue.push(startVertex); // Result array to store the BFS traversal order const result = []; // While there are vertices in the queue while (queue.length > 0) { // Dequeue a vertex from the queue const currentVertex = queue.shift(); // Process the vertex (add to result) result.push(currentVertex); // Get all adjacent vertices of the dequeued vertex // If an adjacent vertex has not been visited, mark it // as visited and enqueue it for (const neighbor of graph[currentVertex]) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor); } } } return result;} // Example usage:const graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']}; const traversalOrder = bfs(graph, 'A');console.log(traversalOrder); // Output: ['A', 'B', 'C', 'D', 'E', 'F']Note: This implementation uses JavaScript's array as a queue. While convenient, using shift() is O(n) time complexity. For large graphs, consider using a proper queue implementation for better performance.
Time and Space Complexity
Time Complexity
O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Explanation: In the worst case, we visit each vertex once (O(V)) and explore each edge once (O(E)). For a connected graph, E is at least V-1, so the time complexity is dominated by the number of edges.
Space Complexity
O(V), where V is the number of vertices in the graph.
Explanation: We need to store the visited set (O(V)) and the queue (O(V) in the worst case). Additionally, we need O(V) space for the result array. Overall, the space complexity is O(V).
Comparison with DFS
Both BFS and DFS have the same time complexity (O(V + E)), but BFS typically requires more memory because it needs to store all vertices at the current level. DFS, on the other hand, only needs to store vertices along the current path, which is typically much smaller.
Applications of BFS
Shortest Path
Finding the shortest path between two vertices in an unweighted graph. BFS guarantees the path with the fewest edges.
Connected Components
Finding all connected components in an undirected graph by running BFS from each unvisited vertex.
Level Order Traversal
Traversing a tree level by level, visiting all nodes at each level before moving to the next level.
Bipartite Graph
Checking if a graph is bipartite (can be colored with two colors such that no adjacent vertices have the same color).
Web Crawling
Crawling web pages and their links, where each page is a vertex and each link is an edge.
Social Networks
Finding all friends within a certain degree of separation, where each person is a vertex and each friendship is an edge.