[29. DFS depth is preferred]

summary

• DFS： Depth-first traversal , Go from one path to the leaf node , Then go back , Continue traversing （ Don't hit the south wall, don't turn around ）
• BFS： Breadth first traversal , From the root node , Layer by layer traversal , Each layer traverses all nodes .

recursive thinking

• Recursion consists in constantly calling your own functions , Layers of depth , Until the recursion termination condition is encountered, layers of backtracking , His thought is related to dfs Our thoughts coincide ; therefore , It can be implemented by recursion dfs.
• Recursive entry is easier to understand , But recursive backtracking is performed at the bottom of the computer , We can't see . So this is the only difficulty in understanding recursion .
  Let's take a look at such a simple recursive program

DFS Solve the full permutation problem

• For the full permutation problem ,n = 3 For example , Conduct DFS Search for ：
  

step 1：

 Suppose there is  3  Empty space , Fill in numbers from front to back , Fill in one place at a time , The number you fill in can't be the same as before .

 At the very beginning , All three empty seats are empty ：__ __ __

 First fill in the first space , The first space can be filled in  1, Fill in as ：1 __ __

 Fill in the first space , Fill in the second space , The second space can be filled in  2, Fill in as ：1 2 __

 Fill in the second space , Fill in the third space , The third space can be filled in  3, Fill in as ： 1 2 3

Now , Fill in the vacancy , Can't continue to fill in , So this is a plan , Output .

step 2：

 Then step back , Back to the State ：1 2 __ . The remaining third space is not filled in . The third space is filled in except  3 , There are no other figures to fill in .

 So take a step back , Back to the State ：1 __ __. The second space is filled in addition to  2, It can also be filled in  3. Fill in the second space  3, Fill in as ：1 3 __

 Fill in the second space , Fill in the third space , The third space can be filled in  2, Fill in as ： 1 3 2

Now , Fill in the vacancy , Can't continue to fill in , So this is a plan , Output .

step 3：

 Then step back , Back to the State ：1 3 __ . The remaining third space is not filled in . The third space is filled in except  2, There are no other figures to fill in .

 So take a step back , Back to the State ：1 __ __. The second space is filled in addition to  2,3, There are no other figures to fill in .

 So take a step back , Back to the State ：__ __ __. The first space is filled in except  1, It can also be filled in  2. Fill in the first space  2, Fill in as ：2 __ __

 Fill in the first space , Fill in the second space , The second space can be filled in  1, Fill in as ：2 1 __

 Fill in the second space , Fill in the third space , The third space can be filled in  3, Fill in as ：2 1 3

Now , Fill in the vacancy , Can't continue to fill in , So this is a plan , Output .

step 4：

 Then step back , Back to the State ：2 1 __ . The remaining third space is not filled in . The third space is filled in except  3, There are no other figures to fill in .

 So take a step back , Back to the State ：2 __ __. The second space is filled in addition to  1, It can also be filled in  3. Fill in the second space  3, Fill in as ：2 3 __

 Fill in the second space , Fill in the third space , The third space can be filled in  1, Fill in as ：2 3 1

Now , Fill in the vacancy , Can't continue to fill in , So this is a plan , Output .

step 5：

 Then step back , Back to the State ：2 3 __ . The remaining third space is not filled in . The third space is filled in except  1, There are no other figures to fill in .

 So take a step back , Back to the State ：2 __ __. The second space is filled in addition to  1,3, There are no other figures to fill in .

 So take a step back , Back to the State ：__ __ __. The first space is filled in except  1,2, It can also be filled in  3. Fill in the first space  3, Fill in as ：3 __ __

 Fill in the first space , Fill in the second space , The second space can be filled in  1, Fill in as ：3 1 __

 Fill in the second space , Fill in the third space , The third space can be filled in  2, Fill in as ：3 1 2

Now , Fill in the vacancy , Can't continue to fill in , So this is a plan , Output .

step 6：

 Then step back , Back to the State ：3 1 __ . The remaining third space is not filled in . The third space is filled in except  2, There are no other figures to fill in .

 So take a step back , Back to the State ：3 __ __. The second space is filled in addition to  1, It can also be filled in  2. Fill in the second space  2, Fill in as ：3 2 __

 Fill in the second space , Fill in the third space , The third space can be filled in  1, Fill in as ：3 2 1

Now , Fill in the vacancy , Can't continue to fill in , So this is a plan , Output .

step 7：

 Then step back , Back to the State ：3 2 __ . The remaining third space is not filled in . The third space is filled in except  1,2, There are no other figures to fill in .

 So take a step back , Back to the State ：3 __ __. The second space is filled in addition to  1,2, There are no other figures to fill in .

 So take a step back , Back to the State ：__ __ __. The first space is filled in except  1,2,3, There are no other figures to fill in .

At this point, the depth first search ends , Output all schemes .

Algorithm

• use path[] Array save arrangement , When the length of the arrangement is n when , It's a scheme , Output .
• use state[] The array indicates whether the number has been used . When state[i] by 1 when ：i Has been used ,state[i] by 0 when ,i Not used .
• dfs(i) It means ： stay path[i] Fill in the number in the box , Then recursively fill in the number in the next position .
• to flash back ： The first i After all the cases of filling in a number in a position are traversed , The first i Fill in the next number in one place .( about for Loop backtracking )

subject

Code

#include <iostream>
using namespace std;

const int N = 10;
int n;
int path[N];          // Save sequence 
bool state[N];        // Indicates the status bit , Not occupied as false, Otherwise true

void dfs(int u )
{
    
    if (u == n)                         // Traverse to the leaf node , Just print 
    {
    
        for (int i = 0; i < n; i ++)
        {
    
            cout << path[i] << " ";      
        }
        cout << endl;
    }
    
    for (int i = 1; i <= n; i ++)         // from 1 Start 
    {
    
        if (!state[i])                    // If the number  i  Not used 
        {
    
            path[u] = i;                  // In the space 
            state[i] = 1;                 // Numbers are used , modify state 
            dfs(u + 1);                   // Fill in the next digit 
            state[i] = 0;                 // to flash back , Take out  i( Here is a trace back to for loop )
        }
    }
}

int main()
{
    
    cin >> n;
    dfs(0);                              // from 0 Start , It means that the subscript of the first number is 0, You can also get it from 1 Start , Personal habits 
    return 0;
}

Link to the original text https://www.acwing.com/solution/content/30988/