算法竞赛专题解析│搜索基础( 四 ) ：算法竞赛专题解析│搜索基

cout<<"inorder:";inorder(E);cout<<endl;//打印中序序列
cout<<"preorder:";preorder(E);cout<<endl;//打印先序序列
cout<<"postorder:";postorder(E);cout<<endl;//打印后序序列
remove_tree(E);
return0;
}
DFS是一直深入的，适合处理节点间的先后关系、连通性等，在图论中应用很广泛。
具体内容，请参考本篇参考书《算法竞赛入门到进阶》第10章图论。
2.DFS代码框架
DFS的代码看起来比较简单，但是逻辑上难以理解，不容易编码。
下面给出DFS的框架。在后续“剪枝”这一篇中的例题“hdu1010TempteroftheBone” ，是非常符合这个框架的示例，请仔细分析例题代码。
读者在大量编码的基础上，再回头体会这个框架的作用。
ans;//答案，用全局变量表示
voiddfs(层数，其他参数){
if(出局判断){//到达最底层，或者满足条件退出
更新答案;//答案一般用全局变量表示
return;//返回到上一层
}
(剪枝)//在进一步DFS之前剪枝
for(枚举下一层可能的情况)//对每一个情况继续DFS
if(used[i]==0){//如果状态i没有用过，就可以进入下一层
used[i]=1;//标记状态i,表示已经用过，在更底层不能再使用
dfs(层数+1 ，其他参数);//下一层
used[i]=0;//恢复状态，回溯时，不影响上一层对这个状态的使用
}
return;//返回到上一层
}
05
BFS和DFS的复杂度
以图为例，图中的所有n个点和所有m条边都应该至少访问一次，所以复杂度至少是O(n+m)的。很多情况下，点和边会计算多次。例如计算图上两个点之间的最短路径，一条路径包含很多点和边，一个点或一个边可能属于不同的路径，需要计算多次，复杂度就会超过O(n+m) 。
在BFS和DFS基础上，发展出了剪枝、记忆化（DFS）、双向广搜（BFS）、迭代加深搜索（DFS）、A*（BFS）等技术，大大增强了搜索的能力。
DFS的代码比BFS更简单，如果一个问题用BFS和DFS都行，一般用DFS 。
搜索的题目，关键往往在于去重。例如BFS的队列，把状态放进队列时，需要判断这个状态是否已经在队列中处理过，如果已经处理过，就不用放进队列，这就是去重。去重能大大优化复杂度。去重用hash很方便，缺点是很浪费空间。
06
参考书籍
《算法竞赛入门到进阶》
ISBN：978-7-302-52915-6
罗勇军郭卫斌编著
定价：59.8元
07
精彩文章回顾
戳下面标题回顾课程
1.连接WiFi和移动网络
2.放大手机字体和调整亮度
3.“打字困难户”？可能是输入法选错了
4.如何用微信给孩子发红包
5.微信和支付宝支付、收费
6.在微信中发朋友圈和点赞
7.微信的语音通话和视频功能
8.智能手机摄影和摄像
9.打车和等公交
10.黑白旧照变彩色照片
算法竞赛专题解析│简单数据机构
算法竞赛专题解析│并查集
算法竞赛专题解析│尺取法
算法竞赛专题解析│二分法、三分法
Spark算法实例：词频统计
大数据集群的部署实例｜附视频
用Excel制作工资条实例｜附素材+视频
真题解析│2017年蓝桥杯软件类省赛传统“送分题”
Java15新增类Record的工作实例｜附代码
Dart应用Bloc设计模式实例｜附代码
从火种到能源，华为做AI的逻辑链
华为AI ，建造中的全景图
逻辑回归的MATLAB实践｜附代码
Python爬虫实例：采集微博博文｜附视频
MySQL利用E-R模型的数据库概念设计｜附视频
HTML5实现黑白棋游戏附代码利用微信小程序实现活动报名登记|附代码使用Flutter小部件跨平台开发移动端App组件|附代码