Complexity Analysis
def bfs(graph, start):
visited = set()
queue = [start]
visited.add(start)
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visitedWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(V + E)
Space
O(V)
How to derive it
Every vertex is enqueued and dequeued at most once → O(V) for vertex processing. Every edge is examined once (when its source vertex is dequeued) → O(E) for edge processing. Total: O(V + E). The visited set and queue together hold at most V elements. Note: queue.pop(0) is O(V) per call — use collections.deque for true O(V + E).