云溪网络建站宝盒,wordpress快速网店主题,wordpress创建博客,微营销app文章目录DFS与BFS区别DFS全排列n皇后BFS树和图的遍历树和图的存储数和图的遍历深度优先遍历宽度优先遍历图的宽搜应用框架DFS与BFS区别
DFS:
执着#xff1a;一直走到头#xff0c;回去的时候边回去边看能不能向下走
BFS:
稳重#xff1a;每次只扩展一层#xff0c;不会…
文章目录DFS与BFS区别DFS全排列n皇后BFS树和图的遍历树和图的存储数和图的遍历深度优先遍历宽度优先遍历图的宽搜应用框架DFS与BFS区别
DFS:
执着一直走到头回去的时候边回去边看能不能向下走
BFS:
稳重每次只扩展一层不会离家太远 算法数据结构空间特征DFSstackO(h)不具有最短性BFSqueueO(2h)、指数级别“最短路”
DFS
DFS中重要概念回溯剪枝
DFS熟称“暴搜”最重要的是需要考虑顺序
画一棵树
全排列
给定一个整数 n将数字 1∼n 排成一排将会有很多种排列方法。现在请你按照字典序将所有的排列方法输出。输入格式
共一行包含一个整数 n。输出格式
按字典序输出所有排列方案每个方案占一行。数据范围
1≤n≤7
输入样例
3
输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1步骤
找到第一个解 回溯 最终结果
没有必要区分DFS与递归DFS就是递归。
虽然看上去是树的形式但存储的话只会存当前路径回溯的时候就没有了。
没有必要把整颗树存储下来。
不需要真的把栈写出来系统会为我们做回溯。写在递归函数中有隐藏栈来维护不需要开额外空间。
回溯中一定要注意恢复现场下来的时候是什么样子回去之后就是什么样子 #include iostream
using namespace std;
const int N 10;int n;
//将状态[路径]存储下来当向下搜时path上数字会逐渐填满
int path[N];
//需要知道当前位置上可以填哪些数即清楚哪些数已经用过了。等于true,表示该点被用过了
bool st[N];void dfs(int u)
{//一开始在第0个位置当到达第n个位置表明均填满此时输出即可if(u n){for(int i 0 ; i n;i) printf(%d ,path[i]);//输出空行puts();return;}for(int i 1;in;i)//找到一个没有被用过的数只有没有用过的才可以使用if(!st[i]){//将数字放到当前位置上去path[u] i;//记录i已经被用过了st[i] true;//将状态处理好后递归至下一层dfs(u1);//dfs结束时表明下面的所有路都走完了就要回溯//回溯时注意恢复现场。出去时什么样回来时什么样回溯后继续运行for循环// path[u] 0没有什么用因为path[u]的值会被不断覆盖掉。不管是几都没问题因此没必要恢复//path[u] 0;st[i] false;}
}int main()
{cinn;dfs(0);return 0;
}n皇后
n− 皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上使得皇后不能相互攻击到即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数 n请你输出所有的满足条件的棋子摆法。输入格式
共一行包含整数 n。输出格式
每个解决方案占 n 行每行输出一个长度为 n 的字符串用来表示完整的棋盘状态。其中 . 表示某一个位置的方格状态为空Q 表示某一个位置的方格上摆着皇后。每个方案输出完成后输出一个空行。注意行末不能有多余空格。输出方案的顺序任意只要不重复且没有遗漏即可。数据范围
1≤n≤9
输入样例
4
输出样例
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..重要的是顺序顺序一定要想清楚 全排列 每一行只有一个皇后 第一行皇后可以放在哪一列 注意剪枝 提前判断当前方案是不合法的停止向下搜索直接回溯 对角线 两种对角线的截距b有两种 y-x:截距不能是负数所以添加偏移量n yx 对角线的数目是2*N-1 #include iostreamusing namespace std;const int N 20;int n;
//存储方案
char g[N][N];
//状态数组列、正对角线、反对角线
bool col[N],dg[N],udg[N];//对行进行遍历
void dfs(int u)
{//当到达第u行当找到一组方案时if(u n){//输出for(int i 0;in;i) puts(g[i]);puts();return;}//从第一列开始枚举for(int i 0 ;in;i)//这一列之前没有放过并且对角线上没有放过并且反对角线上没有放过//i代表yu代表x 反对角线 -xynif(!col[i] !dg[ui] !udg[-u i n]){//在第u行第i列放置皇后g[u][i] Q;//第i列为true表示这一列/对角线/反对角线上已经有皇后了col[i] dg[ui] udg[-uin] true;dfs(u1);//恢复现场col[i] dg[ui] udg[-uin] false;g[u][i] .;}
}
int main()
{cinn;for(int i 0;i n;i)for(int j 0;jn;j)g[i][j] .;dfs(0);return 0 ;
} 时间复杂度n*n 上一种方式经过一步分析即每一行放置一个皇后。 也可以采用一种更原始的方式进行枚举八皇后问题。 一格格枚举每个节点代表一个格子 n2个格子 考虑格子的边界问题如果出界直接返回 时间复杂度2n2 #include iostreamusing namespace std;const int N 20;int n;
//存储方案
char g[N][N];
//状态数组行、列、正对角线、反对角线
bool row[N],col[N],dg[N],udg[N];void dfs(int x,int y,int s)
{//到达y的边界后y置为0跳转至下一行if(y n) y 0,x;//枚举到最后一行需要停止if(x n){//皇后个数等于n找到一组解//s有可能小于n有可能一个皇后都没有摆只有n个皇后才有解if(s n){for(int i 0; in;i){puts(g[i]);}puts();}//注意此处必须有return否则无限递归导致空间不足return;}/*枚举当前格子的两种选择上一种方式有n种选择*///不放皇后直接递归至下一个格子dfs(x,y1,s);//放皇后判断条件if(!row[x] !col[y] !dg[xy] !udg[-x y n]){//更新状态g[x][y] Q;row[x] col[y] dg[xy] udg[-xyn] true;//递归至下一层dfs(x,y1,s1);//恢复现场row[x] col[y] dg[xy] udg[-xyn] false;g[x][y] .;}
}
int main()
{cinn;for(int i 0;i n;i)for(int j 0;jn;j)g[i][j] .;//从左上角开始搜素记录当前一共有多少个皇后dfs(0,0,0);return 0 ;
}
BFS
一圈一圈搜索的距离离当前起点越来越远 给定一个 n×m 的二维整数数组用来表示一个迷宫数组中只包含 0 或 1其中 0 表示可以走的路1 表示不可通过的墙壁。最初有一个人位于左上角 (1,1) 处已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问该人从左上角移动至右下角 (n,m) 处至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0且一定至少存在一条通路。输入格式
第一行包含两个整数 n 和 m。接下来 n 行每行包含 m 个整数0 或 1表示完整的二维数组迷宫。输出格式
输出一个整数表示从左上角移动至右下角的最少移动次数。数据范围
1≤n,m≤100
输入样例
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例
8样例 BFS
每个数字表示它是第几层被扩展到的。 若采用深搜结果不一定对。可以保证找到终点但不能保证是最短的 深搜没有固定框架但宽搜有固定框架。
将初始状态放到队列中写while循环队列不为空 每次把队头拿出来扩展队头结束 假设绿点是队头尝试向上下左右四个方向拓展 用向量表示方向
上 -10//横坐标减一纵坐标不变
右 01//横坐标不变纵坐标加一
下 10//横坐标加一纵坐标不变
左 0-1//横坐标不变纵坐标减一#include iostream
#include algorithm
#include cstring
//一般需要队列此处手写队列
//#include queue
using namespace std;
//用于表示(x,y)
typedef pairint,int PII;
const int N 110;
int n,m;
int g[N][N]; //存储图,不改变图的信息只改变队列
int d[N][N]; //存储每个点到起点的距离
//队列用于存储当前点
PII q[N*N];int bfs()
{//队头hh队尾tt,由于队列中现在存放第一个数据因此tt 0 空队列tt -1;q[0] {0,0};int hh 0 ,tt 0;//初始化为-1memset(d,-1,sizeof d);//从[0,0]点开始走一开始距离为0d[0][0] 0;//四个方向向量int dx[4] {-1,0,1,0},dy[4] {0,1,0,-1}; //队列不为空while(hh tt){//每次取出来队头auto t q[hh];for(int i 0;i 4;i){//(x,y)表示沿着该方向可以走到哪个点int x t.first dx[i],y t.second dy[i];//判断点是否在边界以内 并且 点是可以走的 并且 这个点还没有走过// 如果已经走过表明该点不是第一次搜到bfs是第一次搜到的点才是最短距离// 注意 x的边界为ny的边界为mif(x 0 x n y 0 y m g[x][y] 0 d[x][y] -1){//当前点的距离是之前点的距离加1d[x][y] d[t.first][t.second] 1;//将点添加至队列中q[tt] {x,y};}}}//返回右下角点的距离return d[n-1][m-1];}int main()
{cinnm;//把整个图读进来for(int i 0;in;i )for(int j 0;jm;j)cing[i][j];coutbfs()endl;return 0;}如何显示路径–新建一个变量【数组】存储Prev,记录该位置上的点是由上面哪个点扩展而来的
#include iostream
#include algorithm
#include cstring
//一般需要队列此处手写队列
//#include queue
using namespace std;
//用于表示(x,y)
typedef pairint,int PII;
const int N 110;
int n,m;
int g[N][N]; //存储图,不改变图的信息只改变队列
int d[N][N]; //存储每个点到起点的距离
//队列用于存储当前点
PII q[N*N];
//最后用于显示路径每个点存储上一个点的信息所以每个元素是一个坐标
PII Prev[N][N];int bfs()
{//队头hh队尾tt,由于队列中现在存放第一个数据因此tt 0 空队列tt -1;q[0] {0,0};int hh 0 ,tt 0;//初始化为-1memset(d,-1,sizeof d);//从[0,0]点开始走一开始距离为0d[0][0] 0;//四个方向向量int dx[4] {-1,0,1,0},dy[4] {0,1,0,-1}; //队列不为空while(hh tt){//每次取出来队头auto t q[hh];for(int i 0;i 4;i){//(x,y)表示沿着该方向可以走到哪个点int x t.first dx[i],y t.second dy[i];//判断点是否在边界以内 并且 点是可以走的 并且 这个点还没有走过// 如果已经走过表明该点不是第一次搜到bfs是第一次搜到的点才是最短距离// 注意 x的边界为ny的边界为mif(x 0 x n y 0 y m g[x][y] 0 d[x][y] -1){//当前点的距离是之前点的距离加1d[x][y] d[t.first][t.second] 1;//Prev[x][y]中存储上一个点Prev[x][y] t;//将点添加至队列中q[tt] {x,y};}}}//从结尾向前输出int x n-1,y m-1;//当x y不同时等于0的时候前进。x、y同时为0表明到达起点while(x||y){coutx yendl;//获取上一个点二维点用auto较为方便auto t Prev[x][y];//到达上一个点x t.first,y t.second;}//返回右下角点的距离return d[n-1][m-1];}int main()
{cinnm;//把整个图读进来for(int i 0;in;i )for(int j 0;jm;j)cing[i][j];coutbfs()endl;return 0;}DP问题与最短路问题是互通的dp问题可以看作是一种特殊的最短路问题。
树和图的遍历
树和图的存储
树是一种特殊的图即无环连通图因此只需要考虑图的存储方式即可。
图可以分为有向图与无向图。无向图可以建立两个有向边来表示。因此无向图是一种特殊的有向图。只需要考虑有向图如何存储。 存储方式空间场景邻接矩阵n2适合存储稠密矩阵邻接表[每个节点有一个单链表]
举例四个点开四个单链表。
每个链表存储直接可以到达的点。单链表内部次序是无关紧要的。 当添加新的边时2-3在链表头部进行插入节点 添加后邻接表 注意 邻接表使用数组而不使用vector : vector的效率不如数组快区分使用cin、scanf的场景当输入输出的规模在 100 0000[一百万]时 才必须用scanf否则两者效率都差不多 #include cstring
#include iostream
#include algorithmusing namespace std;
const int N 100010,M N * 2;
/*
h--N个链表的链表头
e--存储链表的值在邻接表中表示连接的节点编号在图中表现为所有的边。
ne--每个节点的next值
*/
int h[N],e[M],ne[M],idx;//插入一条边a-b:即在a节点对应的链表中插入节点b
void add(int a, int b)
{e[idx] b;ne[idx] h[a];h[a] idx;
}int main()
{//链表初始化将所有的链表头初始化为-1即可memset(h,-1,sizeof h);
}
数和图的遍历
遍历时每个点只遍历一次
深度优先遍历
有向图 遍历顺序 #include cstring
#include iostream
#include algorithmusing namespace std;
const int N 100010,M N * 2;
/*
h--N个链表的链表头
e--存储链表的值在邻接表中表示连接的节点编号在图中表现为所有的边。
ne--每个节点的next值
*/
int h[N],e[M],ne[M],idx;//每个点只需要遍历一次需要存储bool数组表示哪些点已经遍历过了
bool st[N];
//插入一条边a-b:即在a节点对应的链表中插入节点b
void add(int a, int b)
{e[idx] b;ne[idx] h[a];h[a] idx;
}//u表示当前已经dfs到的点
void dfs(int u)
{//首先更新状态标记当前点已经被搜索过了st[u] true;//遍历u的所有出边,与遍历单链表相同for(int i h[u];i ! -1; i ne[i]){//获取节点值即对应的图中节点编号int j e[i];//判断条件,如果j没有被搜过则继续搜一条路走到黑if(!st[j]) dfs(j);}
}int main()
{//链表初始化将所有的链表头初始化为-1即可memset(h,-1,sizeof h);//从第一个节点开始搜素dfs(1);
}
846 树的重心
给定一颗树树中包含 n 个结点编号 1∼n和 n−1 条无向边。请你找到树的重心并输出将重心删除后剩余各个连通块中点数的最大值。重心定义重心是指树中的一个结点如果将这个点删除后剩余各个连通块中点数的最大值最小那么这个节点被称为树的重心。输入格式
第一行包含整数 n表示树的结点数。接下来 n−1 行每行包含两个整数 a 和 b表示点 a 和点 b 之间存在一条边。输出格式
输出一个整数 m表示将重心删除后剩余各个连通块中点数的最大值。数据范围
1≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例
4无向图建立相反方向的边输出最小的最大值 举例说明重心是什么 依次枚举删除每个点后剩余部分的最大值
点连通块最大值142645做法 每个点删除后剩余连通块的最大值在所有点中找最小的 深度优先遍历可以快速算出每棵子树的大小
以去除4为例 时间复杂度O(nm)
#include cstring
#include iostream
#include algorithmusing namespace std;
const int N 100010,M N * 2;
/*
h--N个链表的链表头
e--存储链表的值在邻接表中表示连接的节点编号在图中表现为所有的边。
ne--每个节点的next值
*/
int h[N],e[M],ne[M],idx;
int n;
//记录全局的答案表明最小的最大值
int ans N;//每个点只需要遍历一次需要存储bool数组表示哪些点已经遍历过了
bool st[N];
//插入一条边a-b:即在a节点对应的链表中插入节点b
void add(int a, int b)
{e[idx] b;ne[idx] h[a];h[a] idx;
}//dfs返回以u为根的子树中点的数量
//u表示当前已经dfs到的点
int dfs(int u)
{//首先更新状态标记当前点已经被搜索过了st[u] true;//sum:记录当前以u为树根的子树的大小用于返回值 //res:将该点删除后连通块的最大值初始化为0//注定义变量后一定要及时初始化int sum 1,res 0;//遍历u的所有出边,与遍历单链表相同for(int i h[u];i ! -1; i ne[i]){//获取节点值即对应的图中节点编号int j e[i];//判断条件,如果j没有被搜过则继续搜一条路走到黑if(!st[j]){//s表示当前子树的大小int s dfs(j);//当前子树也是一个连通块res max(res,s);//当前子树是以u为根节点树的一部分sum s;}}//计算剩余的连通块的数量 n - sumres max(res, n - sum);//最后res存储删除该点后最大的连通块点数ans min(ans,res);return sum;}int main()
{//处理输入输出cinn;//链表初始化将所有的链表头初始化为-1即可memset(h,-1,sizeof h);for(int i 0;i n;i){int a,b;cinab;add(a,b),add(b,a);}//从第一个节点开始搜素//为什么不是0idx存放的是边也就是下标节点为对应的值。图的节点由输入决定,输入的节点最小为1。以那个点开始搜索都是一样的,以哪个点为根节点均可以dfs(1);coutansendl;return 0;
}
宽度优先遍历
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mTfsenij-1659948153547)(https://gitee.com/jgyong/blogimg/raw/master/img/image-20220808105008157.png)]
847 图中点的层次
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环。所有边的长度都是 1点的编号为 1∼n。 //可以用宽搜求最短路请你求出 1 号点到 n 号点的最短距离如果从 1 号点无法走到 n 号点输出 −1。输入格式
第一行包含两个整数 n 和 m。接下来 m 行每行包含两个整数 a 和 b表示存在一条从 a 走到 b 的长度为 1 的边。输出格式
输出一个整数表示 1 号点到 n 号点的最短距离。数据范围
1≤n,m≤105
输入样例
4 5
1 2
2 3
3 4
1 3
1 4
输出样例
1宽搜图的基本框架
将初始状态放到队列中 --将1号点放至队列中初始化距离[其他点的距离为-1头结点的距离为0]写while循环队列不为空 每次取得队头元素扩展队头扩展所有能到的点 如果x没有被遍历过[因为只有第一次遍历才是最短路径以后的遍历都不是了] x入队更新x的距离 结束 最重要的是关注思想
#include iostream
#include string.husing namespace std;
//有向图节点与边的上限可以都设置为N
const int N 100010;
int n,m;int h[N],e[N],ne[N],idx;
int d[N],q[N];void add(int a,int b)
{e[idx] b;ne[idx] h[a];h[a] idx;
}int bfs()
{//将0节点放置在队列中int hh 0,tt0;//将1号节点放在队列的0号位置q[0] 1;//初始化距离memset(d,-1,sizeof(d));//d[节点]初始化1号节点距离为0d[1] 0;while(hh tt){//取头结点int t q[hh];//拓展每个点的临边for(int i h[t];i ! -1;i ne[i]){//获取节点进行判断int j e[i];if(d[j] -1){d[j] d[t] 1;q[tt] j;}}}return d[n];}int main()
{cinnm;memset(h,-1,sizeof(h));for(int i 0 ;i m;i){int a,b;cinab;add(a,b);}coutbfs()endl;return 0;
}
图的宽搜应用
最经典应用为求拓扑距
848. 有向图的拓扑序列
给定一个 n 个点 m 条边的有向图点的编号是 1 到 n图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列如果拓扑序列不存在则输出 −1。若一个由图中所有点构成的序列 A 满足对于图中的每条边 (x,y)x 在 A 中都出现在 y 之前则称 A 是该图的一个拓扑序列。输入格式
第一行包含两个整数 n 和 m。接下来 m 行每行包含两个整数 x 和 y表示存在一条从点 x 到点 y 的有向边 (x,y)。输出格式
共一行如果存在拓扑序列则输出任意一个合法的拓扑序列即可。否则输出 −1。数据范围
1≤n,m≤105
输入样例
3 3
1 2
2 3
1 3
输出样例
1 2 3拓扑序列针对有向图而言无向图没有拓扑序列
举例 对于每条边起点都在终点前面它就是个拓扑序列。
拓扑序列对应图中每个边都是由前指向后的。 并不是所有的图都有拓扑序列。有环的图没有拓扑序列。
有向无环图一定存在拓扑序列的因此有向无环图又被称为拓扑图。 度数
有向图中每个点有两个度
入度一个点有几条边进来边数叫做入度
出度一个点有几条边出去边数叫做出度 如何求拓扑序列
拓扑序列都是由前指向后入度为0的点都可以作为起点
入度为0没有一条边指向我没有任何一个节点在我前面所有点都可以排在最前面的位置
如果有环的话所有点的入度都不是0 框架
将所有入度为0的点入队宽搜 队列不空 取队头 t枚举t的所有出边 t-j删掉边使得后面节点j的入度–如果j的入度为0[j前面的点都拍好序 放好了]j没有任何限制j入队 没有环的图一定可以依次解决每一个点。 一个有向无环图一定至少存在一个入度为0的点 有向无环图删除一个点后还是有向无环图。
#include cstring
#include iostream
using namespace std;const int N 100010;
int n,m;
int h[N],e[N],ne[N],idx;
//q存储队列
int q[N];
//d存储入度
int d[N];void add(int a,int b)
{e[idx] b,ne[idx] h[a],h[a] idx;
}bool topsort()
{int hh 0,tt -1;//遍历所有点将所有入度为0的点插入到队列中去for(int i 1;i n;i)if(!d[i])//从队尾插入q[tt] i;//while队列不空while(hh tt){//取出队头元素int t q[hh];for(int i h[t];i ! -1;i ne[i]){//找到出边int j e[i];//因为弹出队头所以之后点的入度减一d[j]--;//如果入度为0添加至队列if(d[j] 0) q[tt] j;}}//如果所有点都进入队列表明是有向无环图n个点一开始tt -1//队列中次序就是拓扑序。出队的顺序是拓扑序。出队只是将指针从前向后移动一位前面的顺序都是不变的。因此遍历完成后q中顺序就是拓扑序return tt n-1;
}int main()
{cinnm;memset(h,-1,sizeof h);for(int i 0;i m;i){int a,b;cinab;add(a,b);//更新入度d[b];}if(topsort()){for(int i 0;i n;i) printf(%d ,q[i]);puts();}else puts(-1);return 0;
}题目的答案并不是唯一的
