DSA — BFS

What is BFS?

BFS explores all vertices at the present depth before moving to vertices at the next depth level.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        process(vertex)
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS for Shortest Path

def bfs_shortest_path(graph, start, target):
    visited = set()
    queue = deque([(start, [start])])
    visited.add(start)
    
    while queue:
        vertex, path = queue.popleft()
        
        if vertex == target:
            return path
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None

Time Complexity

Operation	Complexity
Visit all vertices	O(V + E)
Space	O(V)

Use Cases

• Finding shortest path
• Level-order traversal
• Social network connections
• Web crawling

Mini Practice

1. Implement BFS traversal
2. Find shortest path
3. Level-order tree traversal
4. Check if graph is connected

Up Next

Continue with DFS — depth-first search in depth.