原本
小z是打算先写一篇关于字符串的笔记
由于实在是太太太太长了
我决定抛弃它（先丢进草稿箱
然后
这篇稍微正经一点的有关dfs的学习笔记就来辽（这是LDL老师才讲的内容
我来记录一下（记性不太好
语文太差，请多包涵
正文开始
dfs与回溯
Depth First Search
• 深度优先搜索概述
–尽可能“深”的搜索某一分支。在深度优先搜
索中，对于最先发现的结点，如果还有以此为
起点的未搜索边，则沿此边继续搜索下去。当
结点V的所有边都已经被探寻过，搜索将回溯
到发现点V的那条边的始结点。重复此过程直
至源结点可到达的所有结点为止。
• 回溯法概述
–从问题的某一种状态出发, 搜索从这种状态出
发所能达到的所有状态, 当这一条路走到“ 尽
头 ”而没达到目标状态的时候, 再倒回上一个
出发点, 从另一个状态出发, 继续搜索. 这种不
断“走不通就回头”寻找解的方法, 称作“ 回
溯法 ”。
–回溯是搜索算法中的一种控制策略。
–DFS利用的数据结构是栈（stack）。
• 回溯法的基本思想
–为了求得问题的解，先选择某一种可能情况向
前探索，在探索过程中，一旦发现原来的选择
是错误的，就退回一步重新选择，并继续向前
探索，如此反复进行，直至得到解或证明无解。
–如迷宫问题：进入迷宫后，先随意选择一个前
进方向，一步步向前试探前进,如果碰到死胡同，
说明前进方向已无路可走，则返回一步，看看
其它方向是否还有路可走；如果有路可走，则
沿该方向再向前试探，如果仍然无路可走，就
再返回一步看有无其他路可走。按此原则不断
搜索回溯再搜索，直到找到出口或返回到入口
处无解为止。
• 深度优先搜索/回溯法框架一
1 void dfs(当前状态){
2 for (int i =算符最小值; i<= 算符最大值; i++){
3 算符i作用于当前状态，扩展出一个子状态；
4 if ((子状态满足约束条件)&&子状态满足最优性要求)){
5 保存结果;
6 if (到目的地) {
7 if (当前状态为最佳目标状态) 记下最优结果；
8 return; //回溯
9 }
10 dfs(下一个状态);
11 恢复:保存结果之前的状态(回溯一步);
12 }
13 }
14 }
• 深度优先搜索/回溯法框架二
1 void DFS(当前状态){
2 if (当前状态为边界){
3 if (当前状态为最佳目标状态) 记下最优结果；
4 return；//回溯
5 }
6 for (int i =算符最小值; i<= 算符最大值; i++){
7 算符i作用于当前状态，扩展出一个子状态；
8 if ((子状态满足约束条件)&&子状态满足最优性要求)){
9 保存结果;
10 DFS(下一个状态);
11 恢复:保存结果之前的状态(回溯一步)
12 }
13 }
14 }
• 栈的操作（手写 / C++ stack）
（上面是手写，下面是C++ stack）
1 //栈的操作
2
3 //定义栈
4 {
5 int s[MAXN],top=0;
6
7 stack<int>s;
8 }
9 //进栈
10 {
11 s[++top]=num;
12
13 s.push(num);
14 }
15 //出栈
16 {
17 top--;
18
19 s.pop();
20 }
21 //取栈顶元素
22 {
23 num=s[top];
24
25 num=s.top();
26 }
27 //求栈中元素个数
28 {
29 cnt=top;
30
31 cnt=s.size();
32 }
33 //判空
34 {
35 if(top) return true;
36 else return false;
37
38 s.empty();
39 }
40 //清空
41 {
42 top=0;
43
44 while(!s.empty())
45 s.pop();
46 }
今天累了
就这样吧
如果有错误请私信我（今晚有一点迷糊
Good night.
——by_WBCAZ
标签：状态,结点,第一篇,Whisper,top,dfs,搜索,回溯 From： https://www.cnblogs.com/WBCMZ/p/16767237.html