# Thread: Depth-first search & TSP

1. ## Depth-first search & TSP

I've read in a few places (a book I have and online articles) that the running time of Depth-First search is (O(|V| + |E|)), which is linear. In my implementation, I use it to solve the Traveling Salesman Problem, and the running time of Depth-first search grows exponentially, not linear.
Wikipedia notes the time as (O(|V| + |E|)), and I noticed on the side it says O(|V|+|E|) = O(b^d).
http://en.wikipedia.org/wiki/Depth-first_search

Also, doesn't depth-first search traverse all possible paths? So, it will guarantee that the optimal path is found. I've been looking for documentation to confirm this, but I haven't found any yet. In my understanding, it does search all paths. My implementation seems to confirm this.

Thanks.

2. DFS is too general a term to ascribe any particular complexity to it. I'm surprised Wikipedia claims any particular complexity at all. With the TSP, the problem is determining the global minimum. This provably can't be done without examining most of the possible paths, and this has nothing to do with DFS, it's just a fact.

Since TSP is NP-complete, it's certainly not linear in either |V| or |E|...

3. I believe b represents breadth and d represents depth in your b^d formula.

The fun part is that when you're solving TSP, the tree under consideration is not the n cities, but the n! paths; and TSP is indeed linear in n!.

4. Originally Posted by Cpro
I've read in a few places (a book I have and online articles) that the running time of Depth-First search is (O(|V| + |E|)), which is linear. In my implementation, I use it to solve the Traveling Salesman Problem, and the running time of Depth-first search grows exponentially, not linear.
The complexity depends on how you represent the graph. The running time given in Wikipedia assumes an adjacency list representation. Without being very rigorous, the idea is that in exploring the graph, each node is "visited" (in the sense that it's adjacency list is opened) exactly once, and each node's adjacency list is scanned exactly once. The number of nodes is O(|V|) and the sum of the lengths of all of the adjacency lists is O(|E|), hence O(|V| + |E|).

b is the branching factor -- the maximum degree (number of branches) at any node -- and d is the depth (the starting node is depth 0). The maximum possible number of nodes is b^d + b^(d-1) + ... b^0. The maximum number of edges is b^d + b^(d-1) + ... + b^1. Since the b^d term dominates all the lower-order terms, the complexity can be stated as O(b^d). Again, this assumes an adjacency list representation.

If you represent the graph as a matrix, you should be able to get O(|V|^2). If by exponentially, you mean that your DFS is O(something^|V|), that's bad.

5. "DFS is too general a term to ascribe any particular complexity to it. I'm surprised Wikipedia claims any particular complexity at all."

It seems it isn't just Wikipedia either. My data structures book and alot of other websites I've searched also note the time complexity as (O(|V| + |E|)).

"... and TSP is indeed linear in n!."
Can you explain how it is linear in n!.

Edit:
"Without being very rigorous, the idea is that in exploring the graph, each node is "visited" (in the sense that it's adjacency list is opened) exactly once, and each node's adjacency list is scanned exactly once. The number of nodes is O(|V|) and the sum of the lengths of all of the adjacency lists is O(|E|), hence O(|V| + |E|)."

Bear with me while I try to grasp this. Does this mean, that with respect to an adjacent list representation, the running time is (O(|V| + |E|)), while in general terms the running time is exponential?

PS: I use the adjacent list method in my implementation.

Thanks.

6. Originally Posted by Cpro
Does this mean, that with respect to an adjacent list representation, the running time is (O(|V| + |E|)), while in general terms the running time is exponential?

PS: I use the adjacent list method in my implementation.

Thanks.
In general, you can't generalize. The complexity relates to the implementation, not the problem, except in the sense that for some problems you might be able to prove that "Algorithm X" is the most efficient possible algorithm. But even then, it would certainly be possible to come up with a worse algorithm, "Algorithm Y", so Algorithm Y's complexity would be worse than Algorithm X's complexity.

7. Ok, I'm still a bit confused.

Say I calculate the running time of my implementation and graph it, and I find the time complexity is n^2. Does that mean that the running time of my implementation using (O(|V| + |E|)) is also n^2?
Or, are you saying that (O(|V| + |E|)) is independent of the algorithm used (in this case depth-first).

Thanks.

8. > Can you explain how it is linear in n!.
Just what it says -- the running time is a constant times n!. (Actually since you get to have the first city for free, it's really a constant times (n-1)!. But same deal.)

The |V|+|E| representation says that the running time will be a factor for each path you check (it takes some amount of time to check the distance for each path, times the number of paths) plus a factor for getting from one possible solution path to another (the edges between the nodes in your tree, times the number of times you have to change paths).

9. Originally Posted by Cpro
... are you saying that (O(|V| + |E|)) is independent of the algorithm used (in this case depth-first).
Absolutely not. In fact, I'm saying exactly the opposite - the complexity is the complexity of the algorithm, not the complexity of the problem. Furthermore, by algorithm, I mean exactly the specific implementation, not something like "DFS using an adjacency list representation in general". That (what I put in quotes) is not an algorithm, it's a category of algorithms.

Originally Posted by Cpro
Say I calculate the running time of my implementation and graph it, and I find the time complexity is n^2. Does that mean that the running time of my implementation using (O(|V| + |E|)) is also n^2?
Again, no. If your implementation is O(n^2), then it is not O(|V|+|E|). It is possible to write an O(|V|+|E|) implementation of DFS using an adjacency list representation of the graph. It is not guaranteed that every implementation is that efficient. You seem to have written one that isn't. The devil is in the details.

10. Ok, I think I'm starting to understand now. One more question.
Can a DFS implementation ever be faster than (O(|V| + |E|))? I thought big O was an upper bound.

Thank you guys for all the help.
Thanks.

11. No, it's also Theta(|V|+|E|). I wrote O because I was lazy & you only seemed to be interested in the upper bound. Think about it - how could you do any search and be sure that it was complete without traversing every edge and visiting every node at least once?

12. Cpro, I think you may be confusing the complexity of an algorithm and the hardness of a problem. A complexity always refers to the algorithm as RS pointed out. But a problem can be proven to be Hard or Complete for a class such as NP. In this case, there cannot exist a polynomial time algorithm unless P = NP.

13. Originally Posted by brewbuck
DFS is too general a term to ascribe any particular complexity to it. I'm surprised Wikipedia claims any particular complexity at all. With the TSP, the problem is determining the global minimum. This provably can't be done without examining most of the possible paths, and this has nothing to do with DFS, it's just a fact.

Since TSP is NP-complete, it's certainly not linear in either |V| or |E|...
Actually it is linear in |V| and |E|. It just so happens the linear in |V| + |E| is the same as exponential in d.

It sounds counter intuitive but it's correct. It's like saying a 2-exp problem is linear in the number of states, which is true, but the number of states is 2 times exponential in the input size.