DFS算法解析

解题思路:

            对于全排列问题，我们选择深度优先搜索算法（即DFS）实际上是一个递归的思想

下面来讲讲DFS的算法：

                    一、首先对于全排列问题，我们要一个一个节点的找，确保每一个点都没有被漏掉。（DFS没有返回值）

      由图，可以知道，当我在第三层的时候就已经选完了，所以判断截止条件就是x=3+1（即x=n+1)              

    由图，我们也不难看出，当选了第一层之后，第二层的数字不会选第一层重复的，第三层也是一样，那么我就要对使用过的数字做标记，没使用过的也要做标记。（这里我们可以用vis[]数组来做标记，如果该数字没有被选过（即if(！vis[])）那么我将会选它就标记为1，防止下一次循环中我会选到它）

        如果所有数字都选完了之后（1->2->3），需要回溯，回溯后数字要记为没有选过，将vis[]标记为0

       类型题DFS学习连接：https://www.bilibili.com/video/BV14E411q73d?from=search&seid=12160764684049469910

参考代码:

#include int n;//输入的值 
int vis[10];//
int a[10];
void dfs(int x)
{
int i;
if(x==n+1)//判断截止条件,选完了、满足条件了我就可以输出了 
{
for(i=1;i<=n;i++)
printf("%d ",a[i]);//打印遍历结果 
printf("\n"); 
}
for(i=1;i<=n;i++)
{
if(!vis[i])//如果这个数没有被选 
{
vis[i]=1;//那么我就选上它，并标记它，表示我已经选过了 
a[x]=i;//把值存进数组a 
dfs(x+1);//递归,要进入下一层 
vis[i]=0;//走投无路了，要返回，记为0，表示我没选过 
}
}
}
int main()
{
scanf("%d",&n);
dfs(1);//x从第一层开始
return 0;
}