getting the running time of depth first search..

This is a discussion on getting the running time of depth first search.. within the C++ Programming forums, part of the General Programming Boards category; Hi. I need a program solving the running time of depth first search algorithm..I'm trying to solve it but its ...

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    3

    Lightbulb getting the running time of depth first search..

    Hi. I need a program solving the running time of depth first search algorithm..I'm trying to solve it but its hard for me to come up with the solution.
    Is it possible to integrate the backtracking in breadth first search algorithm?
    If so, can you give me any program for this with computation of its running time ??

    I really appreciate any response to this..

    Thnx..

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    What do you mean by "running time"? If you mean the actual CPU time of the program ("algorithm"), then simply time it with some tool. On Linux there is the "time" command to do this.

    If you mean the time complexity (!= running/CPU time), then you consider this using "Big-Oh" notation. If you implement any straightforward DFS algorithm, it will be O(|V| + |E|), where |V| is the number of vertices in the graph and |E| is the number of edges in the graph.

  3. #3
    Registered User
    Join Date
    Dec 2009
    Posts
    3
    hey, thnx for the reply...
    actually, the running time i'm finding is the actual time of the program, I am implementing it on c++ but I don't know how.I know how to get it using java but not in C. by the way, can I get the time in millisec or what?
    and in solving the big-oh notation, can you show me some example? just a short example.
    I really appreciate your response..

  4. #4
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    What OS?

    On *nix just do
    Code:
    time ./your_program
    On Windows it's a bit more complicated. You can use time(), but that will only give you seconds resolution. You'll need clock() (but be careful with that, since it measures different things on different platforms), or WinAPI functions.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    Quote Originally Posted by danillo View Post
    Is it possible to integrate the backtracking in breadth first search algorithm?
    No. A breadth-first algorithm by its nature explores all paths as it goes. Thus there is no use for backtracking in a breadth-first ssearch.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Dec 2009
    Posts
    3
    there is no use for backtracking in bfs but what i'm trying to do is to integrate the backtracking in breadth first search... its some kind a difficult but do you think its possible???

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    Quote Originally Posted by danillo View Post
    there is no use for backtracking in bfs but what i'm trying to do is to integrate the backtracking in breadth first search... its some kind a difficult but do you think its possible???
    You've just acknowledged that there is no use for backtracking in BFS. There's no need to back up and take a different path because you've already taken all paths of the previous length. There's nothing shorter left to try that you haven't already tried, so there's nothing to go back to to recalculate.

    If you insist on proceeding then you probably either do not understand what backtracking is, or what breadth-first-serach is, or both. Or perhaps you're misunderstanding what you've been asked.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need help in time zone
    By Gong in forum C++ Programming
    Replies: 2
    Last Post: 01-03-2007, 03:44 AM
  2. Sending an email in C program
    By Moony in forum C Programming
    Replies: 28
    Last Post: 10-19-2006, 10:42 AM
  3. 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
  4. inputting time in separate compilation
    By sameintheend01 in forum C++ Programming
    Replies: 6
    Last Post: 03-13-2003, 03:33 AM
  5. File Search - more in depth help needed
    By RoD in forum C++ Programming
    Replies: 1
    Last Post: 12-09-2002, 04:48 AM

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