DFS（深度优先搜索）---入门----全排列问题解析---SCAU_LEO

矫情吗；* 2023-06-26 08:19 10阅读 0赞

## 一.个人的一些小感受 ##

唔，这是我第一次发blog，有些小激动，哈哈！（这是应SCAU大数据2班的标哥才开始写的，而且写这个blog有很多好处，我就不一一列举啦）先说一下我对DFS初学的印象，记得我刚开始学DFS的时候，我以为DFS一定是要和树关联起来的，但是我发现并非如此，很多算法都是独立的，可以用在很多地方的，DFS我个人感觉不是很难理解，下面我来说说我个人对DFS的理解。

## 二. DFS理解 ##

![这是一棵树][format_png]  
首先DFS的意思是深度优先搜索，既然要深度优先搜索，那么它肯定要遍历到树的每一个结点，那它是如何遍历的呢？  
1.V0->V1->V2;  
2.V0->v2;  
3.V0->V3->V4;  
4.V0->V3->V5->V6;  
这就是这一棵树对应的遍历情况。  
先做个简单的解释，对于第一种情况，当遍历到V2时，因为V2下面不再有子结点，所以这一条路已经遍历完成了，然后从V2开始回溯到V2，因为V1对应的子结点也都遍历完了，所以再回溯到V0，此时V0对应的子结点V1已经遍历完成，但是V2和V3还未，于是开始遍历V2。V2遍历完后，因为V2此时已经没有子结点，所以V2回溯到V0，同理遍历V3。  
当V3的路遍历完成后，整棵树也就遍历完了，此时算深度优先搜索完成。  
上面就是我对深搜过程的老妈式讲解了- -。  
下面我给出深搜的伪代码和对应每条句子的注意事项和解释。

Boolean visited[max]//访问标志数组
    status(*VisitFunc)(int v);//访问变量
    void DFSTraverse(Graph G,status(*Visit)(int v))
    {
        //对图G作深度优先遍历。
    VisitFunc = Visit;//使用全局变量VisitFunc,使用DFS不必设函数指针参数
    for(v=0;v<G.vexnum;++v) visited[v] = FALSE;//
    for(v=0;v<G.vexnum;++v)
    if(!visited[v]) DFS(G,v)//对尚未访问的顶点调用DFS
    }
    void DFS(Graph G,int v)
    {
        
    //从第v个顶点出发递归地深度优先遍历图G。
    visited[v] = TRUE; 
    visitFunc(v)//访问第v个顶点
    for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,x))
    if(!visited[w]) DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS；
    }
    
    //FirstAdjVex返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”；
    //Next 返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”；

## 三.例题说明 ##

题目的链接：[全排列问题][Link 1]  
题目描述：  
输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式  
n(1≤n≤9)

输出格式  
由1～n组成的所有不重复的数字序列，每行一个序列。每个数字保留5个场宽。

输入输出样例  
输入 \#1 复制  
3  
输出 \#1 复制  
1 2 3  
1 3 2  
2 1 3  
2 3 1  
3 1 2  
3 2 1

说下思路先，对于1，2，3的情况，1可以对应2，3，也可以1，3，2（这两个相当于以1为树的顶点，2，3分别为子结点）。

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<map>
    #include<vector>
    using namespace std;
    int n;
    bool vis[20];//标志数组，看每个结点是否被访问过
    int jl[20]= {
        0};//记录每种情况
    void DFS(int x)
    {
        
      if(x==n+1)//当长度等于要求数的长度+1时输出
      {
        
          for(int i=1;i<=n;i++)
          {
        
              if(i!=n) printf("%5d",jl[i]);//注意题目所属格式宽为5
              else printf("%5d\n",jl[i]);
          }
      }
      else
      {
        
          for(int i=1;i<=n;i++)//访问每个结点
          {
        
              if(!vis[i])//结点未被访问过
              {
        
                  vis[i]=true;//设成已访问
                  jl[x]=i;//记录此时的数字
                  DFS(x+1);//继续深搜
                  vis[i]=false;//这里要注意，一定要每次用完深搜后把vis数组变回去，具体原因自行理解。
              }
          }
      }
    }
    int main()
    {
        
        cin>>n;
        DFS(1);
        return 0;
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTUzNDM4Ny8yMDE4MTIvMTUzNDM4Ny0yMDE4MTIwMTEwMTgxOTIzNC0xNjQ3MzU5NTUxLnBuZw?x-oss-process=image/format,png
[Link 1]: https://www.luogu.com.cn/problem/P1706