学习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) ;
   }

以上代码运行后输出如下（截取部分）

2  J1
3  J2
4  J3
5  J4
6  J5
7  J6
7t
6t
7  J5

问题再最后一句“7 J5”，他表示将进入dfs（7），并且是当前在x=5的时候进入的，但是所写代码里面判断当x=5的时候我并没有让他进入dfs(7),那么他这句输出为什么会这样？结合代码跑一遍，不是应该继续退到上一个x吗？

关于这段switch没有加break，
是的
我是想让他在当前情况继续判断下去

也就是说当他回溯之后，继续根据x的情况判断下去（比如x=5，他还会根据条件情况进入dfs（6）/dfs（4）/dfs（3），如果都不符合条件才跳到末尾结束当前一轮的switch）

按照本例代码运行的理论走势，他应该是退到x=3的情况，然后进入dfs（5）

但他实际情况并不是这样.. 不知道为什么

[此贴子已经被作者于2022-1-21 14:47编辑过]