DFS在非图论算法具体是怎么思考的？

小弟不才 最近刷题的时候 发现很多题目都是属于“dfs”类型的。dfs的概念应该是在图论里吧？ 在普通的非图论算法题里面 一般做起题目来是怎么考虑的呢？比如说求一个String的所有permutation，或者八皇后问题。目前理解下来，就是把当前所有可以得到的解 当做图论中得下一个vertex，然后依次去遍历，是吗？我不知道我的理解对不对。或者还有需要补充的地方？ 还有一般哪些题型 一般都可以通过dfs来做呢？

只要需要求的解可以通过一个序列或者一系列的步骤来表示，就可以用DFS。不过一些情况下DFS需要剪枝，或者是效率太低而使用动态规划等其他方法。

个人一点理解：
当前节点（状态）通过某操作转移到下一节点（状态），进入下一层DFS，完了返回到这一状态时要撤销这一步操作
类似于((()))这种括号序列的感觉，左括号看作1（进行某一操作），右括号看作-1（撤销某一操作），他们是一一对应的，栈的顺序
实现时只考虑其中一层（一个状态）

如果你能把题目抽象成一个图/树，一个节点对应一个状态，状态之间通过某种操作转移，或者需要枚举时，肯定可以用DFS搞定的，具体还是多做题找感觉吧

感觉还有就是DFS比较好实现recursion

典型的题目就是 求出所有XXX 所有路径，all possible results 等等

http://blog.csdn.net/u011095253/article/details/9158387

readman 发表于 2014-1-3 07:50
http://blog.csdn.net/u011095253/article/details/9158387

多谢！

readman 发表于 2014-1-3 07:50
http://blog.csdn.net/u011095253/article/details/9158387

多谢 哈哈~

其实我想问问经常会有题目要求给出 all possible result, 那么我用递归， 如果第一步成立，就递归到下一步，知道满足所有条件就是一个possible result， 这种做法是不是DFS？