Graph Theory37 sections · 1633 units
Open in Course

Articulation Points - Time Complexity

(Linear in edges)

Same as bridges: O(V+E)O(V + E) for DFS traversal. You visit each vertex once and each edge twice (once from each direction). Checking conditions and updating low-link values is O(1)O(1) per edge. Space complexity: O(V)O(V) for recursion stack, discovery times, low-link values, and the result set.

Total: O(V+E)O(V + E). This is best for finding articulation points because you need to examine every edge to determine reachability and connectivity.