返回目录

---

1.DFS

DFS是以递归为主体(说白了就是函数套函数)

DFS的特点

1. 沿着一条路径一直走到底

2. 当无法继续前进时才回溯

3. 确保访问到所有的节点

想象你在走迷宫：

1. 每到一个分岔路口，你总是先选择一条路一直走
2. 走到死胡同时，才返回到最近的分岔路口，选择另一条路

这就是DFS的基本思想

看下面

动态演示，红色为搜索路径，蓝色为回溯路径

DFS的特征

递归性

1. 问题可以分解为子问题
2. 子问题的解决方式与原问题相同
3. 有明确的终止条件

回溯性

1. 当前路径不通时，返回上一步
2. 尝试其他可能的选择
3. 记录和恢复状态

完整性

1. 保证访问所有可能的路径
2. 不会重复访问节点
3. 一定能找到解（如果存在）

他的伪代码如下

void dfs(){
  if(不符合){
      return;
  }
  if(是正确答案){
      保存
      return;
  }
  for(遍历接下来的所有可能){
      打上标记#防止死循环
      dfs();
      删除标记#翻篇了
  }
}

依旧万物皆可搜这一块，考试你就用吧，用一次骗分一次

通用轮椅这一块

2.BFS

BFS是以队列为基础的，一个个遍历的代码，他的好处是只要是无权图，就可以找到最短路径(因为他不是一个个搜的，他是宽度搜索)如下

伪代码如下

void bfs(){
    queue<int>q
    q.push();#将初始值放入队列
    while(!q.empty()){#队列为空就报错啦
        f=q.front();#保存队头
        q.pop()#把原队头删了
        for(遍历所有可能){
            if(这个为答案){#大部分时候其实不需要
                保存答案;
                return;
            }
            if(这个没出界啥的){
                q.push();#先放着，说不定有用！
            }
        }
    }
}

看出啥了没，BFS根本不需要专门写一个函数……

要做题的话把上面的背会就行了，反正他又不考……

难道不考就不用背了吗?谁不想在做不出题目的时候急头白脸的用上DFS骗过所有数据呢?