深度优先搜索（DFS）的基础理解与实现
深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。这种算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
下面是一个简单的DFS实现：
#include<bits/stdc++.h> using namespace std; const int N = 10; int n; int st[N]; int a[N]; void dfs (int u) { if (u == n) { for (int i = 0; i < n; ++ i) cout << a[i] << " "; puts(""); return; } for (int i = 1; i <= n; ++ i) { if (!st[i]) { a[u] = i; st[i] = true; dfs (u + 1); st[i] = false; } } } int main() { cin >> n; dfs (0); return 0; }
在这段代码中，我们定义了一个数组st来记录每个节点是否被访问过，a数组用来记录每次DFS搜索的结果。dfs函数是DFS的主体部分，参数u代表当前正在访问的节点。
在dfs函数中，首先检查当前节点是否是目标节点（u == n），如果是，则打印出当前的搜索结果并返回。如果不是，我们就遍历所有的节点，对于每个未被访问过的节点，我们将其标记为已访问，然后从这个节点开始进行DFS，DFS结束后，我们需要将这个节点的状态重置为未访问。
