深度优先搜索适合解决必须走到最深处(例如对于树，须走到它的叶子节点)才能得到一个解的问题。通常利用递归实现，所以每次递归开始的时候要判断是否达到收敛条件，若达到了则得到一个可行解，若没达到，则对当前状态进行扩展（扩展的时候通常会根据实际情况过滤掉一些非法的状态，这个过程叫剪枝，适当的剪枝有时能极大地提高搜索的速度），如果要求输出具体解，则此时应该保存该状态，当扩展结束后，需要释放这个保存的状态。下面是一个深度优先搜索的编程模板：
/** * dfs 模板. * @param[in] input 输入数据指针 * @param[inout] cur or gap 标记当前位置或距离目标的距离 * @param[out] path 当前路径，也是中间结果 * @param[out] result 存放最终结果 * @return 路径长度，如果是求路径本身，则不需要返回长度 */ void dfs(type *input, type *path, int cur or gap, type *result) { if (数据非法) return 0; // 终止条件 if (cur == input.size( or gap == 0)) { // 收敛条件 将 path 放入 result } if (可以剪枝) return; for(...) { // 执行所有可能的扩展动作 执行动作，修改 path dfs(input, step + 1 or gap--, result); 恢复 path } }下面用Leecode上一个具体的问题来说明深度优先搜索算法：
实现的程序如下：
#include "stdafx.h" #include <iostream> #include <vector> #include <string> using namespace std; class Solution { public: vector<vector<string> > solveNQueens(int n) { column=vector<int>(n,0); principle_diagonals=vector<int>(2*n,0); counter_diagonals=vector<int>(2*n,0); vector<int> C(n,0); //C[i]的值表示第i行皇后所在的列 vector<vector<string>> result; DFS(result,C,0); return result; } private: vector<int> column; //column[i]表示第i行皇后所在的列 vector<int> principle_diagonals; //表示主该主对角线是否已经有皇后 vector<int> counter_diagonals; //表示副对角线是否已经有皇后 void DFS(vector<vector<string> >& result,vector<int>&C ,int row) { int n=C.size(); if(row==n) //收敛条件 { string tmpStr(n,'.'); vector<string>tmpResult(n,tmpStr); for(int i=0;i<n;++i) { tmpResult[i][C[i]]='Q'; } result.push_back(tmpResult); return; } for(int i=0;i<n;++i) { bool ok=column[i]==0&&principle_diagonals[row+i]==0 && counter_diagonals[n-row+i]==0; if(ok) //用于剪枝，只扩展合法的状态 { //执行扩展 column[i]=principle_diagonals[row+i]=counter_diagonals[n-row+i]=1; C[row]=i; DFS(result,C,row+1); //撤销扩展 column[i]=principle_diagonals[row+i]=counter_diagonals[n-row+i]=0; C[row]=0; } } } }; int _tmain(int argc, _TCHAR* argv[]) { vector<vector<string>> result; Solution sln; result=sln.solveNQueens(4); for (int i=0;i<result.size();++i) { for (int j=0;j<result[0].size();++j) { cout<<result[i][j]<<endl; } cout<<endl; cout<<endl; } return 0; } 对于4皇后，上述程序输出结果如下：
