Time and Space Complexity
Lesson 7 of 9 in Coddy's Breadth-First Search - Graph Algorithms course.
Time Complexity:
- O(V + E)
- Every vertex is enqueued and dequeued once, and each edge is examined a constant number of times.
Space Complexity:
- O(V + E)
- The adjacency list stores every edge, and the queue and visited array hold up to V vertices.
Summary:
- BFS explores in layers using a queue, visiting nearer vertices before farther ones.
- That layered order makes it the go-to algorithm for shortest paths in unweighted graphs.
Try it yourself
This lesson doesn't include a code challenge.
Test yourselfThis lesson includes a short quiz. Start the lesson to answer it and track your progress.
All lessons in Breadth-First Search - Graph Algorithms
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity