I'm always confusing these concepts. They're very very confusing me.
1. DFS is one of ways of search in graph and it can be implemented by recursive function. Moreover I always believe (recursive function = Backtracking).
So I think Backtracking is high concept than DFS and Backtracking is not a algorithm, but just a programming technique like DP.
2. Divide & Conquer is paradigm for algorithm design. It can be implemented by Backtracking and DP.
3. D&C > Backtracking > DFS
Am I right?
Oh.. There is another question.
Are there any problems that I could solve by ONLY using Backtracking?
Please help me.
ps. Hmm...My English is very poor. sorry about that.
Backtracking , DFS, Divide & Conquer
Moderator: Board moderators
-
白約
- New poster
- Posts: 2
- Joined: Sun Jan 08, 2006 7:39 pm
DFS != recursion
You don't need recursion for DFS - you can use a stack. Just like you use a queue for BFS.
DFS applies to a well-defined graph in which you can easily identify back-edges -- ones that revisit vertices you've already dealt with.
This makes DFS linear time. In general "recursive" solutions can be exponential but obviously the recursive implementation of DFS is not.
Some DFS-derived algorithms, like topological sort, are pretty obvious. Some, like biconnected components, are not. [CLR had a wrong algorithm for many years; I presume it is now fixed]
DFS applies to a well-defined graph in which you can easily identify back-edges -- ones that revisit vertices you've already dealt with.
This makes DFS linear time. In general "recursive" solutions can be exponential but obviously the recursive implementation of DFS is not.
Some DFS-derived algorithms, like topological sort, are pretty obvious. Some, like biconnected components, are not. [CLR had a wrong algorithm for many years; I presume it is now fixed]