自问自答
通过以下问题,加深对dfs的理解。
自问
- dfs进行递归,表示的意义?
- 如何加深对dfs的理解(求法)?
- 为何回溯时,进行现场的恢复?
自答
- 此题中dfs表示的含义是:
求出从第u行到最后一行的所有path
。 - dfs的求法:根据通项公式的含义,假设
已知第u+1行到最后一行的所有path
,综合1和2得出:path[u] 与 path[u+1] 合并后,即为dfs的解。 - 回溯的特征是:递归的最外层是一个循环。因为一次dfs得到的是所有的path。每一次都是从当前现场中去取得剩下未访问的元素。(这一块自己画个图就很容易理解)。
反证:如果不进行现场的恢复,则在第一次完成深搜后,所有元素都已经被访问过了。
这样在回溯到上一层时,上层的现场中的状态都被下层更改了,数据就会乱套。
#include <iostream>
using namespace std;
const int N = 10;
int path[N];
bool st[N];
int n;
// 计算u->n的所经过的路径path
void dfs(int u)
{
// 边界条件
if (u == n)
{
for (int i = 0; i < n; i++) printf("%d ", path[i]);
puts("");
return;
}
else
{
for (int i = 1; i <= n; i++)
{
if (!st[i])
{
path[u] = i;
st[i] = true;
dfs(u+1); // 回溯之后,为何要恢复现场?
path[u] = 0;
st[i] = false;
}
}
}
}
int main()
{
scanf("%d", &n);
dfs(0);
return 0;
}
回溯保证return回来后,该i位置不会被重复使用
回溯的解释写的太好了, 当前层开分支要保证当前层的现场,不能被下层影响,从而保证每条路径独立。
每一次都是从当前现场中去取得剩下未访问的元素,st[]数组并不控制回溯,而是简单记录记录当前路径访问过的元素。
### 谢谢 ###
###666
很有帮助,谢谢
那个,我把15行的for条件改成了for(int i=0;i<n;++i)
然后再把主函数dfs改成1为什么就不对了呢。?
i 在循环里面的操作执行的和i是同样的加1操作,只是++i的速度快一些.... 还是要dfs(0)
en差不多了。谢谢啊。
还有。。。恢复现场可还星
path[u] = 0; 这一步感觉可以不用。因为下次赋值,直接覆盖了 你说呢~?
应该是吧
初学者写着方便理解
主要因为每层只对st[]有判断,没有对path数组的判断,改不改path不影响dfs回溯