algorithmgraphtime-complexitybreadth-first-search

Breadth First Search time complexity analysis


The time complexity to go over each adjacent edge of a vertex is, say, O(N), where N is number of adjacent edges. So, for V numbers of vertices the time complexity becomes O(V*N) = O(E), where E is the total number of edges in the graph. Since removing and adding a vertex from/to a queue is O(1), why is it added to the overall time complexity of BFS as O(V+E)?


Solution

  • I hope this is helpful to anybody having trouble understanding computational time complexity for Breadth First Search a.k.a BFS.

    Queue graphTraversal.add(firstVertex);
    
    // This while loop will run V times, where V is total number of vertices in graph.
    while(graphTraversal.isEmpty == false)
    
        currentVertex = graphTraversal.getVertex();
    
        // This while loop will run Eaj times, where Eaj is number of adjacent edges to current vertex.
        while(currentVertex.hasAdjacentVertices)
            graphTraversal.add(adjacentVertex);
    
        graphTraversal.remove(currentVertex);
    

    Time complexity is as follows:

    V * (O(1) + O(Eaj) + O(1))
    V + V * Eaj + V
    2V + E(total number of edges in graph)
    V + E
    

    I have tried to simplify the code and complexity computation but still if you have any questions let me know.