dfs深度优先遍历（全排列，数独）
（1）全排列
1.什么是全排列从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
2.例子假设现在有一个数组ar如下
ar[3]={1,2,3};那么这个数组的全排列就是
1,2,31,3,22,1,32,3,13,1,23,2,1
#includeusingnamespacestd;intn;inta[100]={0};intflag[100]={0};//用于标志1-n已经被使用与否intdfs(inttimes){//cout深度以及广度优先遍历树
广度优先遍历-----以二叉树为例广度优先遍历需要额外的数据结构–队列，来存放临时遍历到的元素。特点是层层扫荡。所以，我们需要先将根节点放入到队列中，然后不断的迭代队列中的元素。/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(intx){val=x;}*}*///递归classSolution{publicListlevelOrder(TreeNoderoot){Listres=newArrayList();if(root==null){returnres;}levelOrderHelper(root,0,res);returnres;}privatevoidlevelOrderHelper(TreeNodenode,intlevel,Listres){if(node==null){return;}if(level>=res.size()){res.add(newArrayList());}res.get(level).add(node.val);levelOrderHelper(node.left,level+1,res);levelOrderHelper(node.right,level+1,res);}}在以上代码中，我们使用一个辅助函数levelOrderHelper来递归地进行二叉树的广度优先遍历。对于每个节点，我们将其值添加到相应的层级列表中，然后递归遍历其左右子节点，并将层级加一。注意，我们使用一个level参数来表示当前节点的层级，以便将其值添加到正确的列表中。同时，我们还使用一个res列表来保存所有层级的节点值列表。在主函数中，我们检查根节点是否为空，然后调用levelOrderHelper函数进行遍历。最后，我们将res列表返回作为结果。
/*非递归*///将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素LinkedListqueue=newLinkedList();queue.add(root);while(!queue.isEmpty()){//具体当前结点的操作//每次都从队列中拿一个节点，并交换这个节点的左右子树TreeNodetmp=queue.poll();/*TreeNodeleft=tmp.left;tmp.left=tmp.right;tmp.right=left;*///如果当前节点的左子树不为空，则放入队列等待后续处理if(tmp.left!=null){queue.add(tmp.left);}//如果当前节点的右子树不为空，则放入队列等待后续处理if(tmp.right!=null){queue.add(tmp.right);}深度优先遍历-----以二叉树为例深度优先遍历的特点是一竿子插到底，不行了再退回来继续；
“深度遍历函数体”–“空转”,相关操作通过某种手段保存
/*递归*/classSolution{publicListpreorderTraversal(TreeNoderoot){Listres=newArrayList();dfsPreorder(root,res);returnres;}privatevoiddfsPreorder(TreeNodenode,Listres){if(node==null){return;}res.add(node.val);//以加一个元素为例dfsPreorder(node.left,res);dfsPreorder(node.right,res);}/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(intx){val=x;}*}*///非递归classSolution{publicListpreorderTraversal(TreeNoderoot){Listres=newArrayList();if(root==null){returnres;}Stackstack=newStack();stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();res.add(node.val);if(node.right!=null){stack.push(node.right);}if(node.left!=null){stack.push(node.left);}}returnres;}}在以上代码中，我们使用栈来模拟递归过程，先将根节点入栈，然后每次弹出栈顶节点，将其值加入结果列表，再依次将右子节点和左子节点入栈。由于栈是后进先出的结构，所以先将右子节点入栈，这样才能保证左子节点在右子节点之前被访问到，从而实现前序遍历的效果。
C++深度优先搜索（DFS）详解
今天我带给大家的是深度优先搜索，全拼：DepthFirstSearch，简写DFS
目录认识DFS经典题型总结开始了哦，认真看认识DFSDFS的基本思想就是递归其过程为沿着每一个可能的路径向下进行搜索，直到不能再深入为止，并且每一个节点只能访问一次如果还不理解就看下面懂了吗，懂了就继续往下看吧！
经典题型1.迷宫信息学奥赛一本通1215迷宫链接可以试着去看题分析思路：用朴素的办法:就是用两个下标去判断，从而存在一个数组中用深搜的办法:定义一个递归，下标在变，到了就返回知识点做上面相似的一些题，都会用上一些知识首先，我们需要一个方向数组，好来判断前面方向可不可以走因为深搜的性质就是暴力枚举
方向数组怎么定义呢?用数组，例如迷宫其实就是可以上下所有如果向右那么x坐标轴就增加1，y坐标轴不变如果向上那么x坐标轴就不变，y坐标轴增加1如果向左那么x坐标轴就增加-1，y坐标轴不变如果向下那么x坐标轴就不变，y坐标轴增加-1那么就是
intdx[]={0,0,1,-1}intdy[]={1,-1,0,0}记得一定要对应上有了方向数组，基本就可以了但是要注意，还得判断一下这个位置被走过没有，不然就会卡死在这喽代码
#include#includeusingnamespacestd;intt,n,sx,sy,ex,ey;//起点位置和终点位置charans[101][101];//存储当前位置是否可以走boolv[101][101],flag;//判断这个位置走没走过，flag就是这次是否能走到终点intdx[]={0,0,1,-1};//方向数组intdy[]={1,-1,0,0};voiddfs(intx,inty){//深度优先搜索函数if(x==ex&&y==ey){//边界条件，到终点那么将flag变为是，并且返回flag=true;return;}for(inti=0;icin>>t;while(t--){cin>>n;for(inti=0;icin>>ans[i][j];}}cin>>sx>>sy>>ex>>ey;v[sx][sy]=1;//将起点赋值为被走过flag=false;//默认不能走到终点memset(v,0,sizeof(v));//每次判断完都要将v数组所有元素赋值为没走过dfs(sx,sy);cout//如果已经满了，就不放了，输出cout//判断字符是否被使用过v[a[i]]=1;//使用当前字符，所以要赋值为使用过b[step]=a[i];//给b数组赋值dfs(step+1);//赋值下一位v[a[i]]=0;//回溯}}}intmain(){cin>>a;dfs(0);//已使用0个字符,所以传参为0return0;}学会了吗？练习一下组合的输出吧代码可以发在评论区
总结深度优先搜索（DFS）的性质是暴力枚举，基本思想是递归
你们期待我的下一篇文章吗？期待就动一动你的小鼠标，为我点个赞，加个关注吧!!!
图的深度优先搜索c++
题目描述已知有向图G的顶点和边，输出图的深度优先遍历结果(从1号结点开始)
输入输入的第一行两个整数n,m。n表示节点个数,节点用1-n表示，m表示边的条数，第二行起的m行每行有两个数s，t表示边的起点和终点。(m intneighbor=graph[node][i]; if(!visited[neighbor]){ dfs(graph,visited,neighbor); } }}
intmain(){ intn,m; cin>>n>>m;
vectorgraph(n+1); vectorvisited(n+1,false);
for(inti=0;i>s>>t; graph[s].push_back(t); }
for(inti=1;i dfs(graph,visited,i); } }
return0;}