DSA — Graph Traversal

BFS (Breadth-First Search)

Explores all neighbors at current depth before moving deeper.

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)

DFS (Depth-First Search)

Explores as far as possible along each branch before backtracking.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start)
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

BFS vs DFS

Feature	BFS	DFS
Data Structure	Queue	Stack/Recursion
Approach	Level by level	Branch by branch
Use Case	Shortest path	Cycle detection

Mini Practice

1. Implement BFS
2. Implement DFS
3. Find shortest path with BFS
4. Detect cycles with DFS

Up Next

Continue with BFS — breadth-first search in depth.