Time and Space Complexity
Lesson 7 of 9 in Coddy's Depth-First Search - Graph Algorithms course.
Time Complexity:
- O(V + E)
- Building the adjacency list touches every edge once, and the traversal visits every vertex and looks at each edge a constant number of times.
Space Complexity:
- O(V + E)
- The adjacency list stores every edge, and the visited array and stack each hold up to V vertices.
Summary:
- DFS explores deeply first, backtracking when it runs out of unvisited neighbors.
- It runs in linear time and is the backbone of many graph algorithms.
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 Depth-First Search - Graph Algorithms
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity