搜索·从入门到入土

本蒟蒻由于一开始搜索没学好，所以深受其荼毒……并且由于最近很闲，所以打算整理整理搜索算法这个大毒瘤……如果搜索学不好，没准$NOIp$连暴力也不会$qwq$. ~~虽然可以直接写正解不暴力~~ 好啦不扯淡了$qwq$,下面记录记录心得 # 一.最普通的$dfs$和$bfs$ 一般比较高级的考试都不可能直接考察这两种算法，但是是非常重要的基础工作。在这里整理一下相关的“$unfamiliar$ $points$” ## $dfs$: ### 1、关于回溯 这个问题是$dfs$里的核心问题，因为在深搜树中，回溯好像是一个很显然的操作，但是有时候却有不同的写法（以下内容太小学生） 比如第一种，这种格式就是典型的回溯： ```cpp void dfs(step) { … … … … … … visit[now]=1; step++; dfs(step); visit[now]=0; step--; … … … … … … } ``` 当然也有第二种 ```cpp void dfs(step) { … … … … … … dfs(step+1); … … … … … … } ``` 这两种是等价的啦，虽然有些略微的不同，但是……只是略微。 ### $PS:$关于$return$不$return$的问题 实际有时候加不加$return$效果一样，原因就是在全部搜索完之后，程序会自动回溯；但是这个地方只是一个小知识而已，并不能盲目不$return$…………因为搜索完一定会$return$，但是$return$却不一定要搜索完。 ### 2、关于剪枝 这个应该不难，因为是要根据题目而言的策略，所以无非就是发现到什么时候越界，到什么时候的搜索是无效的，$return$就行。 ### 3、关于几种很蒟蒻的$dfs$题型 #### 1)数列去重题： 比如某年的一道水题，求一个数的所有加和组成方式，不能重复。那我们如果单纯地回溯，会很难去重。那我们这个时候可以想出一个小技巧：虽然这个结果数列不是单调的，但是我们可以将其看作单调数列。那么这样的话，由于单调性，既可以枚举所有情况，又可以防止之后搜索出的与之前的有重复。 #### 2)树的遍历题： 由于肯定会给定后序遍历或先序遍历，所以我们就可以很显然地看出根节点在哪，那么不断切换中序遍历与先后序遍历，递归下去即可。 #### 3)求联通块题： 遇到这种求联通块的题，首先考虑染色。但是染色也可以分成多染色和01染色……视题而定了。(这就是典型的可不回溯$dfs$) 当然辣，还会有好多奇奇怪怪的用法$qwq$