Exploring Time Complexity of the Breadth First Search Algorithm

Breadth-First Search (BFS) is a traversal algorithm that explores a graph or tree level by level, starting from a given source node.

It uses a queue data structure to keep track of nodes to be visited next. The algorithm works by visiting all the nodes at a given level before moving on to the next level.

def bfs_traversal(adj_list, vertex):
    traversal_seq = []
    visited = set()
    deque = [vertex]
    while queue:
        current_vertex = deque.pop(0)
        # Visit each vertex
        if current_vertex not in visited:
            traversal_seq.append(current_vertex)
            visited.add(current_vertex)
            # Iterating over edges
            queue.extend([v for v in adj_list[current_vertex] if v not in visited])
    return traversal_seq

vector<int> bfs_traversal(int start_vertex) {
    vector<int> traversal_seq;
    unordered_set<int> visited;
    queue<int> q;
    q.push(start_vertex);

    while (!q.empty()) {
        int current_vertex = q.front();
        q.pop();
        
        // Visit each vertex
        if (!visited.count(current_vertex)) {
            traversal_seq.push_back(current_vertex);
            visited.insert(current_vertex);

            // Iterate over edges
            for (auto neighbor : adj_list[current_vertex]) {
                if (!visited.count(neighbor)) {
                    q.push(neighbor);
                }
            }
        }
    }
    return traversal_seq;
}

Time Complexity of BFS

The time complexity of this algorithm can be broken down into two parts:

1. Visiting Each Vertex

This algorithm visits each vertex once, which takes constant time, O(1), per vertex. Since there are V vertices, the total time complexity of visiting each vertex is O(V).

2. Iterating Over Edges

BFS also iterates over the neighbors of each vertex, which takes time proportional to the number of edges, E. Since each edge is visited once, the total time complexity of iterating over the edges is O(E).

Overall Time Complexity: O(V + E)

Thus, the overall time complexity of the BFS algorithm is the sum of the time complexity of visiting each vertex and iterating over edges, which is O(V + E).

Factors Affecting Time Complexity

While the time complexity of BFS is O(V + E), there are some factors that can affect its performance:

1. Graph Density

In a dense graph, the number of edges, E approaches <katex>V^{2}</katex>, where V is the number of vertices which makes the time complexity <katex>O(V + V^{2})</katex>.

Since <katex>V^{2}</katex> dominates V, it becomes <katex>O(V^{2})</katex>.

2. Graph Sparsity

In a sparse graph, E and V are almost equal. Thus, the complexity is closer to O(V) as very few edges need to be explored.