Why is the time complexity of both DFS and BFS O( V + E )

Understanding O(V + E) Time Complexity in DFS and BFS

Explore why Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms exhibit O(V + E) time complexity, a fundamental concept in graph theory.

Depth-First Search (DFS) and Breadth-First Search (BFS) are two of the most fundamental algorithms for traversing or searching graph or tree data structures. Despite their different exploration strategies—DFS goes deep before backtracking, while BFS explores level by level—both algorithms share the same asymptotic time complexity: O(V + E), where 'V' represents the number of vertices (nodes) and 'E' represents the number of edges in the graph. This article delves into the reasons behind this shared complexity, breaking down how each component (V and E) contributes to the overall runtime.

The Role of Vertices (V)

The 'V' component in O(V + E) accounts for the work done at each vertex. Both DFS and BFS must visit every vertex in the graph at least once (assuming the graph is connected from the starting point). When a vertex is visited, the algorithm typically performs a constant amount of work:

• Marking as visited: To prevent infinite loops in graphs with cycles and to ensure each vertex is processed only once, algorithms mark vertices as 'visited'. This is a constant-time operation.
• Adding to a data structure: DFS uses a stack (either explicitly or implicitly via recursion), and BFS uses a queue. Adding a vertex to these structures is typically a constant-time operation.
• Processing data: Any application-specific processing for that vertex (e.g., printing its value, checking a condition) is also considered constant time per vertex for the purpose of complexity analysis.

Since each of the 'V' vertices is visited and processed a constant number of times, the total time spent on vertex-related operations is proportional to V, hence O(V).

flowchart TD
    A[Start Traversal]
    B{Is current vertex V visited?}
    C[Mark V as visited]
    D[Perform constant work on V]
    E[Add V to stack/queue (DFS/BFS)]
    F[Explore neighbors of V]
    A --> B
    B -- No --> C
    C --> D
    D --> E
    E --> F
    B -- Yes --> G[Skip V]
    F --> H{Are all vertices processed?}
    H -- No --> A
    H -- Yes --> I[End Traversal]

Flowchart illustrating the processing of a single vertex in DFS/BFS.

The Role of Edges (E)

The 'E' component accounts for the work done traversing the edges. Both DFS and BFS explore the edges to find unvisited neighbors. The way this exploration happens depends on the graph's representation:

• Adjacency List Representation: This is the most common and efficient representation for sparse graphs (graphs with relatively few edges compared to the maximum possible). For each vertex u, we iterate through its adjacency list to find its neighbors. If u has deg(u) neighbors, iterating through its list takes O(deg(u)) time. Since each edge (u, v) appears in u's adjacency list and v's adjacency list (for undirected graphs) or just u's list (for directed graphs), each edge is effectively 'looked at' a constant number of times across all adjacency list traversals. Summing deg(u) for all u gives 2E for undirected graphs and E for directed graphs. Thus, the total time spent iterating through adjacency lists is proportional to E, hence O(E).

• Adjacency Matrix Representation: In this representation, checking for an edge between u and v takes O(1) time. However, to find all neighbors of u, we must iterate through all V possible columns (or rows) in u's row (or column) in the matrix. This takes O(V) time for each vertex. If we do this for all V vertices, the edge-related work becomes O(V*V) or O(V^2), which is less efficient than O(E) for sparse graphs. However, for dense graphs (where E approaches V^2), O(V^2) is equivalent to O(E).

Given that adjacency lists are generally preferred for graph traversals due to their efficiency with sparse graphs, the O(E) term is derived from iterating through these lists.

Combining V and E: Why O(V + E)?

The total time complexity is the sum of the work done on vertices and the work done on edges. Each vertex is visited once, and each edge is examined a constant number of times (twice for undirected graphs in an adjacency list representation, once for directed graphs). Therefore, the total time complexity is O(V + E).

It's important to note that V and E are not always independent. In a connected graph:

• The minimum number of edges is V - 1 (for a tree).
• The maximum number of edges is V * (V - 1) / 2 for an undirected simple graph, or V * (V - 1) for a directed simple graph.

This means that E can be as small as O(V) or as large as O(V^2). The O(V + E) notation accurately captures the complexity across this spectrum, as it accounts for both the vertex processing and the edge traversal, regardless of the graph's density.

from collections import deque

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        vertex = queue.popleft() # O(1) for deque
        print(vertex) # Constant work per vertex

        for neighbor in graph[vertex]: # Iterating through edges
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor) # O(1) for deque

def dfs_iterative(graph, start_node):
    visited = set()
    stack = [start_node]
    visited.add(start_node)

    while stack:
        vertex = stack.pop() # O(1) for list.pop()
        print(vertex) # Constant work per vertex

        for neighbor in graph[vertex]: # Iterating through edges
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor) # O(1) for list.append()

# Example Graph (Adjacency List)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("BFS Traversal:")
bfs(graph, 'A')
print("\nDFS Traversal (Iterative):")
dfs_iterative(graph, 'A')

Python implementation of BFS and iterative DFS, highlighting vertex and edge operations.