Time complexity of bfs and dfs

#1

how is the time complexity of bfs and dfs equal to O(v+e) if we consider this code

while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();

    // Get all adjacent vertices of the dequeued 
    // vertex s. If a adjacent has not been visited,  
    // then mark it visited and enqueue it 
    for (i = adj[s].begin(); i != adj[s].end(); ++i) 
    { 
        if (!visited[*i]) 
        { 
            visited[*i] = true; 
            queue.push_back(*i); 
        } 
    } 
}

the time complexity should be O(ve) or O(ev)
how loop is executing here pls explain.

#2

Hey @121dcabingoel BFS can only be used to find shortest path in a graph if:

  • There are no loops
  • All edges have same weight or no weight.

To find the shortest path, all you have to do is start from the source and perform a breadth first search and stop when you find your destination Node. The only additional thing you need to do is have an array previous[n] which will store the previous node for every node visited. The previous of source can be null.

#3

If you still have any doubt, you can ask me :grinning:

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#5

bro, the link is not working

#6

Which link @121dcabingoel?