最近在刷一些算法题,发现DFS在单链表,二叉树,图,集合的解题比较多,具有一定的通用规律,现在讲通用方法记录下。拿二叉树举例,比如我们需要从根走到叶子节点才能得到一个解,这种类型非常适合是用DFS,再以二维数组举例,我们可以将二维数组当成一个图,进行搜索,在搜索的同事满足一定的匹配等。
一般情况下Wide-FS只要求有一个解,而且需要将整个中间状态存储到内存中,而DFS只存储一条路径,非常时候解决一些问题。
在DFS中我们需要一个收敛条件,也就是合法解。这时我们就需要把这个中间状态保存到最后的结果中。为了加快深搜,我们可以剪枝,常用方式使用状态数组表示,提前return,可以大大加快递归速度。
通用dfs模板:
/** * dfs 模板. * @param[in] input 输入数据指针 * @param[out] path 当前路径,也是中间结果,可以是一维数组 * @param[out] result 存放最终结果,二维数组 * @param[inout] cur or gap 标记当前位置或距离目标的距离,或者可以 * 是start end等标记 * @return 路径长度,如果是求路径本身,则不需要返回长度 * 可以返回bool等,依照题目要求来实现。 */ void dfs(type &input, type &path, type &result, int cur or gap) { if (数据非法) return 0; // 终止条件 if (cur == input.size()) { // 收敛条件 // if (gap == 0) { 将path 放入result } if (可以剪枝) return; for(...) { // 执行所有可能的扩展动作 执行动作,修改path dfs(input, step + 1 or gap--, result); 恢复path } }
这里我举一个例子:列举所有set可能的子集合,比如S=[1,2,3],那么结果是[[3],[2],[1],[1,2,3],[1,3],[2,3],[1,2],[]]
解决这个问题,需要首先按照上面的这种模板构建,首先是这个dfs的input 也就是这个S,中间路径path与S类型相同。结果应该是一个二维数组,也就是vector< vector > result,最后我们需要一个step作为收敛条件。
void dfs(const vector<int> &S, vector<int> &path, vector<vector<int> > &result,int step) { if (step == S.size()) {//到达S.size()收敛 result.push_back(path); return; } //这里没有剪枝 // 不选S[step] subsets(S, path, step + 1, result); // 选S[step] path.push_back(S[step]); subsets(S, path, step + 1, result); path.pop_back(); } void dfs(vector<int>& nums,vector<int> &path,vector<vector<int>> &result, vector<int>::iterator start){ result.push_back(path); for(auto i = start;i<nums.end();i++) { path.push_back(*i); dfs(nums,path,result,i+1); path.pop_back(); } }
深度搜索比较难以理解,层层递归会让我迷失,不过进行断点认真跟踪是可行的。最后跟踪断点结果是:
[] 3 2 2,3 1, 1,3 1,2 1,2,3
还有很多场景,比如二维数组寻路,都会用到上下左右的移动,还要使用flag来标示,具体查看
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/word-search/