Time Complexity Of BFS

#1

Sir, can you explain me the time complexity of BFS using adjacency list?

#2

You go to each node only once. (remember we keep visited array, thus never go to a node again)

1 Like
#3

Okay, and then in the worst case we are checking for each edge if node is visited, that’s why O(v+e) right?

#4

Yeah right…