5.24

dfs深度优先搜索：

思想比较简单，就是一条路走到底，走到最深点处再回退一步，再看有没有路可以走，没有的话再回退一步，重复此步骤；
也是人们常讲的暴搜。

主要的用法：

通常需要一个状态数组来记录每次走路时侯的状态，如果走过就将他变成true，再走完之后，需要回头的情况就需要将其变成原来状态，如false；

            state[i] = true;//修改状态

            dfs(u + 1);//填下一层的位置

            state[i] = false;//回溯,返回上一层的状态

重要的是dfs的顺序，从哪里开始，从哪一层开始；

例题：https://www.acwing.com/solution/content/30988/

对输入的数进行全排列：

#include "iostream"

using namespcae std;

const int N =10;

int p[N];//用来记录所有结点的所有值；

bool st[N]//记录状态；

void dfs(int u){

  if(u==n){

  //如果到达了最下面的一层，也就是满足了所有值都试了一遍，那么就是输出的条件

      for(int i = 0;i<n;i++)cout<<p[i]<<" ";

  cout<<endl;

  }for(int i =1;i<=n;i++){

  //因为是对1~n的全排列，所以这里从i=1开始

      if(!st[i]){

      //如果当前位置的值是没有被尝试过的

          p[u]=i;

          //将p数组对应的位置，进行赋值，这里的u是指层数，

          st[i] =true;

          dfs(u+1);

          st[i] =false;

      }

  }

}

int main(){

  cin>>n;

  dfs(0);

  //意思就是从0位置处开始进行结点的遍历

  return 0;

}

巴特西

磊磊零基础打卡算法：day20 c++dfs树的深度优先遍历

5.24

最新文章

热门文章