Breadth First Search vs Depth First Search

Breadth First Search (BFS) and Depth First Search (DFS) are the two fundamental algorithms for traversing or searching tree and graph data structures. They differ in the order they visit nodes and the data structures they rely on internally.

Breadth First Search (BFS)

BFS explores all neighbors of a node before moving to the next level, using a queue to track nodes to visit. It finds the shortest path in terms of number of edges in unweighted graphs.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

Depth First Search (DFS)

DFS explores as far as possible along a branch before backtracking, using a stack (explicit or via recursion).

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

Comparison Table

Complexity