Printable View
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..:o
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.
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..
What OS?
On *nix just do
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.Code:time ./your_program
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.Quote:
Originally Posted by danillo
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.Quote:
Originally Posted by danillo
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.