DFS、BFS和Backtracking模板

Bertha 。 2022-07-15 03:43 183阅读 0赞

# 搜索问题的解法 #

1.  DFS（深度优先搜索）
2.  BFS（广度优先搜索）
3.  backtracking（回溯）

# DFS模板 #

void dfs(...) 
    {
        // 结束递归的条件
        if (...) {
            ..... // 把“当前结果” 加入 “结果集容器” 中
            return;
        }
    
        // 继续递归，里面可能有回溯，也可能没有
        if (...) {
    
            ... // 在容器中保存当前数据
            dfs() 
            ... // 在容器中删除上面保存的数据（注：这种情况下就称为回溯，很明显它是dfs的一个步骤）
        }
    }

## 难点 ##

1.  寻找dfs结束条件
2.  继续dfs的条件

## 题目 ##

[78. Subsets][]  
[93. Restore IP Addresses][]

# BFS模板 #

## 模板1 ##

void bfs(...)
    {
        queue q;
        q.push(startRoot);
        while (!q.empty()) {
            // 按照节点处理
            curNode = q.front();
            q.pop();
    
            if (...) {
                // 处理curNode,并把curNode的相邻Nodes加入队列
            }
        }
    
    }

## 模板2 ##

void bfs(...)
    {
        queue q;
        q.push(startRoot);
        while (!q.empty()) {
            // 按照层次处理
            size = q.size();
            for (i = 0; i < size; i++) {
                curNode = q.front();
                q.pop();
    
                if (... ) {
                    // 处理curNode,并把curNode的相邻Nodes加入队列
                }
            }
        }
    
    }

## 题目 ##

[199. Binary Tree Right Side View][]

# 参考 #

[Restore IP Addresses][]

[78. Subsets]: https://leetcode.com/problems/subsets/
[93. Restore IP Addresses]: https://leetcode.com/problems/restore-ip-addresses/
[199. Binary Tree Right Side View]: https://leetcode.com/problems/binary-tree-right-side-view/
[Restore IP Addresses]: http://www.cnblogs.com/yuzhangcmu/p/4106686.html