Depth-First Search (DFS)

DFS is a concept in graph theory, please see DFS (graph theory) for details. In searching algorithms, this term usually refers to an algorithm that uses recursive functions to implement a brute force enumeration. It has certain similarities with the DFS algorithm in graph theory, but not exactly the same.

Let's consider this example:

sample problem

Divide the positive integer n into 3 different positive integers, such as 6=1+2+3 , and the number in the back must be greater than or equal to the number in the front. Please output all possible solutions with operands in the right hand side sorted ascendingly.

For this problem, what should I do if I don’t know about the search?

Of course use a 3-fold loop. The sample code is as follows:

for (int i = 1; i <= n; ++i)
  for (int j = i; j <= n; ++j)
    for (int k = j; k <= n; ++k)
      if (i + j + k == n) printf("%d=%d+%d+%d\n", n, i, j, k);

What if we need to divide it into four integers? Add another cycle?

What about dividing into integers less than or equal to m ?

This is when the recursive search is needed.

The characteristic of this type of search algorithms is that the target to be searched is divided into several "layers", and each layer makes decisions based on the state of the previous layers until the target state is reached.

Let's look back to the example above. Suppose a solution divide the positive integer n into the sum of k integers, namely k positive integers a_1, a_2, \ldots, a_k .

We seperate the problem into layers, and the i-th level determines a_i . In order to make decisions at the i -th level, we need to record three state variables: n-\sum_{j=1}^i{a_j} , which represents the sum of all positive integers; a_{i-1 } , which represents the positive integer of the previous layer to ensure that the positive integer increases; and i , which is to ensure that we output at most m positive integers.

To store the solution, we use the arr array, in which the i -th item represents a_i . Note that arr is actually a stack of length i .

Code show as below:

int m, arr[103];  // arr is used to record the solution
void dfs(int n, int i, int a) {
  if (n == 0) {
    for (int j = 1; j <= i - 1; ++j) printf("%d ", arr[j]);
    printf("\n");
  }
  if (i <= m) {
    for (int j = a; j <= n; ++j) {
      arr[i] = j;
      dfs(n - j, i + 1, j);  // Please think about this line of code carefully
    }
  }
}
// main function
scanf("%d%d", &n, &m);
dfs(n, 1, 1);

Sample problem

Luogu P1706 Permutation problem (original link in Chinese)

C++ code:

bool vis[N];  // visited array
int a[N];     // permutation array to store the current search results in order

void dfs(int step) {
  if (step == n + 1) {  // boundary
    for (int i = 1; i <= n; i++) {
      cout << setw(5) << a[i];
    }
    cout << endl;
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i] == 0) {
      vis[i] = 1;
      a[step] = i;
      dfs(step + 1);
      vis[i] = 0;
    }
  }
  return;
}
buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments