Graph BFS
MediumBreadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the current depth before moving to the next level. Useful for finding shortest paths in unweighted graphs.
Time Complexity
O(V + E)Space Complexity
O(V)Category
Graph
Introduction to Breadth-First Search (BFS)
BFS is a graph traversal algorithm that explores vertices in layers - first visiting all neighbors, then all neighbors of neighbors. It's essential for finding shortest paths in unweighted graphs and is widely used in real applications.
How It Works
BFS uses a queue (FIFO) to explore the graph:
1. Start with a vertex and add it to queue
2. Mark it as visited
3. While queue is not empty:
- Remove front vertex from queue
- For each unvisited neighbor:
- Mark as visited
- Add to queue
4. Continue until queue is empty
Algorithm Complexity
Key Characteristics
1. Uses queue (FIFO) for processing
2. Explores all neighbors at current distance before moving further
3. Finds shortest path in unweighted graphs
4. Visits nodes level by level
5. Always finds solution if it exists
Advantages
1. Finds shortest paths in unweighted graphs
2. Guarantees finding the minimum distance
3. Can be used for connectivity problems
4. Good for level-order traversal
5. Often faster in practice than DFS
6. Suitable for bipartite checking
Disadvantages
1. Uses more memory than DFS (stores all nodes at current level)
2. Slower for finding connectivity in deep graphs
3. Cannot easily find all paths (unlike DFS)
4. May use more memory for wide graphs
When to Use
Applications
Variations
1. **Bidirectional BFS**: Search from both ends
2. **0-1 BFS**: Handle weights of 0 and 1
3. **Multi-source BFS**: Start from multiple vertices
4. **Level-order traversal**: BFS on trees
BFS vs DFS
|---------|-----|-----|
Key Takeaways
- Explores level by level
- Uses queue for traversal
- Finds shortest paths
- Good for connectivity problems
- All vertices are explored
- Guarantees shortest path in unweighted graphs
Implementation
function bfs(graph, start) {
const visited = new Set();
const queue = [start];
visited.add(start);
while (queue.length > 0) {
const v = queue.shift();
console.log(v);
for (let neighbor of graph[v] || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return visited;
}