CODEWITHSUNDEEP
algorithmdata-structuresgraph-theorydepth-first-searchdirected-acyclic-graphs
j.i.l.l
j.i.l.l

Reputation: 11

Time complexity of DFS on DAG without using a visited array

What would be the worst-case time complexity for Depth first search on a Directed Acyclic graph with V nodes and E edges if I do not use something like a visited array and traverse same nodes multiple times?

Upvotes: 0

Views: 1012

Answers (1)

Dillon Davis
Dillon Davis

Reputation: 7740

I believe that the worst-case graph would be one where you repeatedly form acyclic "diamonds" like A->B, A->C, B->D, C->D, such that when at A, you're presented with two paths to get to D. Chaining these together, you'd end up with an exponential number of paths to explore. Specifically, you'd end up with O(2^(n/3)) time complexity to explore such a graph.

I'm not entirely certain that a 2-node choice is the worst, but it does at least provide an upper bound on the worst case time.

Upvotes: 3

Related Questions