DSA — Breadth First Search

What is 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()
        print(vertex)
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Shortest Path

def bfs_shortest(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)

Applications

• Shortest path in unweighted graph
• Level-order traversal
• Social network connections
• Web crawling

Mini Practice

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

Up Next

Continue with Dijkstra's Algorithm — weighted shortest path.