给出如图3-1所示的图，求图中的V0出发，是否存在一条路径长度为4的搜索路径。
图3-1
显然，我们知道是有这样一个解的：V0->V3->V5->V6。
这里先给出上边处理过程的对应伪代码。
Cpp代码 /** * DFS核心伪代码 * 前置条件是visit数组全部设置成false * @param n 当前开始搜索的节点 * @param d 当前到达的深度，也即是路径长度 * @return 是否有解 */ bool DFS(Node n, int d){ if (d == 4){//路径长度为返回true，表示此次搜索有解 return true; } for (Node nextNode in n){//遍历跟节点n相邻的节点nextNode， if (!visit[nextNode]){//未访问过的节点才能继续搜索 //例如搜索到V1了，那么V1要设置成已访问 visit[nextNode] = true; //接下来要从V1开始继续访问了，路径长度当然要加 if (DFS(nextNode, d+1)){//如果搜索出有解 //例如到了V6，找到解了，你必须一层一层递归的告诉上层已经找到解 return true; } //重新设置成未访问，因为它有可能出现在下一次搜索的别的路径中 visit[nextNode] = false; } //到这里，发现本次搜索还没找到解，那就要从当前节点的下一个节点开始搜索。 } return false;//本次搜索无解 }
此后堆栈调用返回到V0那一层，因为V1那一层也找不到跟V1的相邻未访问节点
此后堆栈调用返回到V3那一层
此后堆栈调用返回到主函数调用DFS(V0,0)的地方，因为已经找到解，无需再从别的节点去搜别的路径了。
这里先给出DFS的核心代码。
Cpp代码 /** * DFS核心伪代码 * 前置条件是visit数组全部设置成false * @param n 当前开始搜索的节点 * @param d 当前到达的深度 * @return 是否有解 */ bool DFS(Node n, int d){ if (isEnd(n, d)){//一旦搜索深度到达一个结束状态，就返回true return true; } for (Node nextNode in n){//遍历n相邻的节点nextNode if (!visit[nextNode]){// visit[nextNode] = true;//在下一步搜索中，nextNode不能再次出现 if (DFS(nextNode, d+1)){//如果搜索出有解 //做些其他事情，例如记录结果深度等 return true; } //重新设置成false，因为它有可能出现在下一次搜索的别的路径中 visit[nextNode] = false; } } return false;//本次搜索无解 }
当然了，这里的visit数组不一定是必须的，在一会我给出的24点例子中，我们可以看到这点，这里visit的存在只是为了保证记录节点不被重新访问，也可以有其他方式来表达的，这里只给出核心思想。
深度优先搜索的算法需要你对递归有一定的认识，重要的思想就是：抽象！
可以从DFS函数里边看到，DFS里边永远只处理当前状态节点n，而不去关注它的下一个状态。
它通过把DFS方法抽象，整个逻辑就变得十分的清晰，这就是递归之美。
上面的文章来自大神：
本文为原创，转载请注明出处：rapheal@iteye
作者：raphealguo(at)qq.com
这个大神讲的比较浅显易懂，算了对dfs有了那么一点点的了解。做的题目是计蒜客上的一个题目。
求整数X。 6 6 1 2 3 4 5 6 4 看到的博客是用dfs解决的。看了书，问了别人才有了那么一点的大致了解。想到了未名湖畔的烦恼。现在对dfs和动态规划都不懂。
