0

I had a question abt the running time of DFS. i know its O(n + m) but according to wikipedia, there is another running time given: O(b^d). what is the difference btw the two or is it the same representation.

this is what was written in wikipedia:"O(|E|) for explicit graphs traversed without repetition, O(b^d) for implicit graphs"

Dominique Fortin
  • 2,212
  • 15
  • 20
ueg1990
  • 1,003
  • 2
  • 19
  • 39
  • See http://stackoverflow.com/questions/6850357/explanation-of-runtimes-of-bfs-and-dfs. – Mihai8 Aug 12 '13 at 16:12
  • i understand why running time is O(V+E). i want to know what is different abt running time O(b^d). are these both running times related?? – ueg1990 Aug 12 '13 at 17:49

1 Answers1

0

Most of what you work with in your typical algorithms class will be explicit graphs, but these may not be representations common in the real world.

For these explicit graphs, depth first search has a runtime of O(V + E) (or O(n + m), same thing); here, V represents the number of vertices that you have in your graph and E represents the number of edges that you have in your graph. This should intuitively make sense, since depth first search is a traversal algorithm used to traverse an entire graph in a depth first search manner, where we backtrack after hitting a dead end for the traversal algorithm. Okay, but this is the easy part.

The weirder part that you're not used to seeing is the implicit graph representation of DFS. According to Wikipedia at this moment, when it comes to searching algorithms, "an implicit graph may be defined as a set of rules to define all neighbors for any specified vertex." This can be seen in the neighborhood representations part of the article. Implicit graphs are simply just defined implicitly and may be infinite or very large, whereas explicit graphs are finite and given in advance. Implicit graphs are great for searching up to a certain depth, which is what I will get to in my next point.

https://en.wikipedia.org/wiki/Implicit_graph

Now that we have a basic idea of what implicit graphs themselves are, we can talk about the running time for DFS that you've seen. For DFS, when we say the running time is O(b^d) for implicit graphs, realize that the DFS algorithm itself still works pretty much the same way.

Here, "b" stands for the branch factor and "d" stands for the depth-level. We simply want the algorithm to only go to a certain depth level. Facebook's method of finding mutual friends could be a good example for this. If we want our direct friends, the depth-level would be 1. If we want friends of our friends, the depth level would be 2. The Rubik's cube puzzle could also be used as an "implicit graph" for DFS traversal, depending on the current state of the cube and future possible moves. Chess is also be a great example of this.

Saying O(V + E) is a correct upper bound for implicit graphs, but we could be more precise with the O(b^d) bound, stating that we have essentially taken DFS only to a certain depth for the implicit graph. Since the implicit graph is very large or even infinite, this should make sense as to why we don't want the pure O(V + E) example.

aryar
  • 1
  • 1