Depth-first search & TSP

This is a discussion on Depth-first search & TSP within the C++ Programming forums, part of the General Programming Boards category; I've read in a few places (a book I have and online articles) that the running time of Depth-First search ...

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    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
    Can someone please explain this?

    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.
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    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|...
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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. #4
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    Quote Originally Posted by Cpro View Post
    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. #5
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    "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.
    Last edited by Cpro; 12-12-2008 at 10:12 PM.
    IDE - Visual Studio 2005
    Windows XP Pro

  6. #6
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    Quote Originally Posted by Cpro View Post
    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. #7
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    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.
    IDE - Visual Studio 2005
    Windows XP Pro

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    > 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. #9
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    Quote Originally Posted by Cpro View Post
    ... 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.

    Quote Originally Posted by Cpro View Post
    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. #10
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    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.
    IDE - Visual Studio 2005
    Windows XP Pro

  11. #11
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    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. #12
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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. #13
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Quote Originally Posted by brewbuck View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21