本帖最后由 1847292359 于 2022-1-21 14:50 编辑
楼主在学习深度搜索回溯，碰到了一个好奇怪的问题，我附上图和代码一起描述问题，大家结合两者看一下
我跟着代码边跑边分析，并且用cout输出以便理清代码执行状况，问题在输出那句“7 J5”， 他表示将进入dfs（7），并且是当前在x=5的时候进入的，但是所写代码里面判断当x=5的时候我并没有让他进入dfs(7),那么他这句输出为什么会这样？结合代码跑一遍，不是应该继续退到上一个x吗？
是代码写得有问题还是我理解dfs有问题呢？（代码是C++写的简单dfs）
[C++] 纯文本查看 复制代码 #include<bits/stdc++.h>
using namespace std;
bool yg[7];
//yg = 用过 用来判断的
void dfs(int x)
{
yg[x] = 1;//每来一次就先占了他 后面再释放
switch(x) {
case 1:
if(!yg[2]){
cout<<"2 J"<<x<<endl;//J=叫他进的数
dfs(2) ;
}
if(!yg[4]){
cout<<"4 J"<<x<<endl;
dfs(4) ;
}
case 2:
if(!yg[3]){
cout<<"3 J"<<x<<endl;
dfs(3) ;
}
if(!yg[7]){
cout<<"7 J"<<x<<endl;
dfs(7) ;
}
case 3:
if(!yg[4]){
cout<<"4 J"<<x<<endl;
dfs(4) ;
}
if(!yg[5]){
cout<<"5 J"<<x<<endl;
dfs(5) ;
}
if(!yg[7]){
cout<<"7 J"<<x<<endl;
dfs(7) ;
}
case 4: if(!yg[5]){
cout<<"5 J"<<x<<endl;
dfs(5) ;
}
if(!yg[3]){
cout<<"3 J"<<x<<endl;
dfs(3) ;
}
case 5: //问题这里
if(!yg[6]){
cout<<"6 J"<<x<<endl;
dfs(6) ;
}
if(!yg[4]){
cout<<"4 J"<<x<<endl;
dfs(4) ;
}
if(!yg[3]){
cout<<"3 J"<<x<<endl;
dfs(3) ;
}
case 6:
if(!yg[5]){
cout<<"5 J"<<x<<endl;
dfs(5) ;
}
if(!yg[7]){
cout<<"7 J"<<x<<endl;
dfs(7) ;
}
case 7:
if(!yg[6]){
cout<<"6 J"<<x<<endl;
dfs(6) ;
}
if(!yg[3]){
cout<<"3 J"<<x<<endl;
dfs(3) ;
}
if(!yg[2]){
cout<<"2 J"<<x<<endl;
dfs(2) ;
}
}
yg[x] = 0;//这次用完了 释放
cout<<x<<"t"<<endl;//t表示退出 即x退出了
}
int main(){
dfs(1) ;
}
就是每次dfs完了之后他应该退回到上一个让他进入dfs的地方继续执行下去，但是这里为什么会出现这种情况？
按照本例代码运行的理论走势，他应该是一直退到x=3的情况，然后进入dfs（5）
但他实际走向并不是这样，不知道为什么
希望大家可以解答下，一直搞不明白 | 
[复制链接]
发表于 2022-1-21 14:15
|
发表于 2022-1-21 14:37
