Data StructuresIntermediate18 min readUpdated March 2025

BFS & DFS

Breadth-First Search (BFS) and Depth-First Search (DFS) are the two fundamental graph traversal algorithms. BFS explores level by level using a queue; DFS explores as deep as possible using a stack (or recursion). Together they solve hundreds of graph problems.

Breadth-First Search (BFS)

BFS explores all neighbors of a node before moving to the next level. It uses a queue (FIFO) to process nodes in order of their distance from the source.

Key properties: - Visits nodes in order of increasing distance from the source - Guarantees the shortest path (in terms of number of edges) in unweighted graphs - Time complexity: O(V + E) - Space complexity: O(V) for the queue and visited set

Applications: - Shortest path in unweighted graphs - Level-order tree traversal - Finding connected components - Web crawlers - Social network "degrees of separation"

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to track the path.

Key properties: - Explores one path completely before trying another - Does NOT guarantee shortest path - Time complexity: O(V + E) - Space complexity: O(V) for the recursion stack

Applications: - Detecting cycles - Topological sort - Finding connected components / strongly connected components - Maze solving - Generating permutations/combinations (backtracking)

BFS and DFS Implementations

Complete implementations of both algorithms:

python

from collections import deque, defaultdict

# ---- BFS - Shortest Path ----
def bfs_shortest_path(adj, start, end):
    """Returns shortest path from start to end (unweighted graph)"""
    if start == end:
        return [start]
    visited = {start}
    queue = deque([(start, [start])])   # (node, path)

    while queue:
        node, path = queue.popleft()
        for neighbor, _ in adj[node]:
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return []   # No path found

# ---- DFS - Recursive ----
def dfs_recursive(adj, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    result = [start]
    for neighbor, _ in adj[start]:
        if neighbor not in visited:
            result.extend(dfs_recursive(adj, neighbor, visited))
    return result

# ---- DFS - Iterative (using explicit stack) ----
def dfs_iterative(adj, start):
    visited = set()
    stack = [start]
    result = []
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            result.append(node)
            for neighbor, _ in adj[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    return result

# ---- Number of Connected Components ----
def count_components(n, edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append((v, 1))
        adj[v].append((u, 1))

    visited = set()
    count = 0
    for node in range(n):
        if node not in visited:
            dfs_recursive(adj, node, visited)
            count += 1
    return count

Topological Sort (DFS-based)

Topological sort orders vertices of a DAG such that for every directed edge u -> v, u comes before v. Used for dependency resolution (build systems, package managers):

python

# ---- Topological Sort (Kahn's Algorithm - BFS) ----
def topological_sort_kahn(n, prerequisites):
    """
    n: number of courses (0 to n-1)
    prerequisites: [[a, b]] means b must come before a
    """
    in_degree = [0] * n
    adj = defaultdict(list)

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1

    # Start with all nodes that have no prerequisites
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []   # Empty if cycle detected

# Course schedule: can you finish all courses?
print(topological_sort_kahn(4, [[1,0],[2,0],[3,1],[3,2]]))
# [0, 1, 2, 3] or [0, 2, 1, 3]

# ---- Cycle Detection in Directed Graph ----
def has_cycle_directed(adj, n):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(node):
        color[node] = GRAY   # Currently being processed
        for neighbor in adj[node]:
            if color[neighbor] == GRAY:   # Back edge = cycle!
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK   # Fully processed
        return False

    return any(dfs(i) for i in range(n) if color[i] == WHITE)

Key Takeaways

BFS uses a queue and finds shortest paths (by edge count) in unweighted graphs.
DFS uses a stack (or recursion) and is used for cycle detection, topological sort, and backtracking.
Both BFS and DFS have O(V + E) time complexity and O(V) space complexity.
Kahn's algorithm (BFS-based topological sort) also detects cycles — if not all nodes are processed, a cycle exists.
For grid problems, BFS finds the shortest path; DFS explores all possible paths.

Contact Us

Have a question or feedback? Fill out the form below or reach us directly at support@nvaitraining.com