引入

DFS是什么？

以下是来自维基中关于Depth-first search的介绍：

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.

也就是说，当我们把问题具象为一个网的时候，DFS可以让我们循着网的一条路径尽可能深的去遍历这个网，并根据每一步搜索的结果来决定接下来的步骤，最终在当前的路径的尽头回溯并开始另一路径的搜索。
于是，能够得出它有以下性质:

1. 为了求得问题的解，先选择某种情况向前探索当前的网；
2. 一直向前，当发现搜索到的解是错误的，就退回一步，重新向前探索；
3. 如此循环往复，直到发现问题无解或者找到正确的解。

DFS的操作过程

首先，我们假设有点V1-V9。
在当前状态中，我们假设V1-V9都未被访问，如下图:

我们先开始访问V1，此时V1被标记:

现在与V1相邻的点有V2与V3两个，我们任选一个:

此时的路径为V1->V2。

当进行到V2时，与V2相邻的节点有V1,V4与V7，但V1现在已经被标记使用，所以在V4与V7中继续任选一个:

此时的路径为V1->V2->V4。

当进行到V4时，与V4相邻的节点有V2与V5，但V2同样已经被标记使用，所以现在能够搜索的节点只有V5了:

此时的路径为V1->V2->V4->V5。

随后，我们发现只有V7没有被访问，于是开始走向节点V7:

此时的路径为V1->V2->V4->V5->V7。

如你所见，现在在节点V7出发，已经找不到未被搜索的点了。
在这种情况下，DFS会进行回溯。聪明如你，应该能够猜到DFS会回溯到最近的且连接有未访问节点的节点，事实也确实如此。
所以此时DFS按照原路回溯到点V1，现在它能够发现点V3未被访问，于是开始访问V3:

此时的路径为V1->V2->V4->V5->V7->V3
同样的道理，继续搜索点V6，并在下一步任选一个，假设选择搜索节点V8:

此时的路径为V1->V2->V4->V5->V7->V3->V6->V8。

继续搜索V9:

此时的路径为V1->V2->V4->V5->V7->V3->V6->V8->V9。

于是我们发现我们遇到了在V7节点同样的状况，于是有同样的处理方法：按照先前所搜索过的顺序回溯，现在我们发现全部节点都已经被搜索过了。
现在，DFS就会结束这一次的搜索。

从流程中可以得到，通常来说DFS的最差时间复杂度为$O(n!)$。

来举个例子！

以Luogu P1706为例，我们通过它来增进对DFS的理解。该段代码写作参考了DFS(搜索)- OI Wiki中的思路。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include<iostream>
#include<iomanip>
#define MAXN 114
using namespace std;
int n,search[MAXN]; //初始化记录查找次数的变量及存储查找到的数据的数组
bool vis[MAXN]; //记录当前执行状态

void dfs(int step)
  {
      if (step==n+1) //设置边界，记录遍历执行末的退出条件
      {
          for(int i=1; i<=n; i++)
          {
              cout << setw(5) << search[i]; //设置场宽并输出每段结果 
          }
          cout << endl;
          return;
       }
          for (int i=1; i<=n; i++)
          {
          if (vis[i] == 0) //判断数字i是否正在目前执行的全排列中
          {
              vis[i]=1; //标记当前节点
              search[step]=i; //存储结果到数组
              dfs(step+1); //进行递归
              vis[i]=0; //重置状态，方便下一步回溯
          }
      }
      return;
  }

int main()
{
  cin >> n;
  dfs(1); //设置起始步数
  return 0;
}

听起来似乎有点抽象…那么我们来一点一点分析。
以题目中给出的样例数据为例，我们可以同样将问题具象为具有三个节点的树。就像这样:

自1开始，我们依旧任选其一来搜索:

此时的路径为1->2

搜索的步骤对应递归代码中进行递归的部分，继续传递搜索结果并进行相应的回溯。
接下来的步骤就像上文中提到的那样，回溯到节点1并且搜索节点3:

此时搜索到的结果就是"1 2 3"并输出。周而复始，搜索到该排列下所有的可能性之后，就从节点2开始继续遵循上文DFS的原则开始搜索。

参考资料

算法分析 | 一文理解搜索算法-彻底入门DFS - 知乎
深度优先搜索（DFS）算法详解
DFS (深度优先搜索) 算法详解 + 模板 + 例题，这一篇就够了 - CSDN
DFS(搜索)- OI Wiki P1706 全排列问题 - 洛谷