本文共 9607 字,大约阅读时间需要 32 分钟。
搜索与图论 一
搜索与图论 一
DFS 和 BFS
1.深度优先搜索 DFS
2.宽度优先搜索 BFS
对比 :
数据结构 空间
DFS : stack O( h ) 不具有 “最短路” 性质
BFS : queue O( 2^h ) 具有 “最短路” 性质 当边的权重为 1 的时候 , 第一次搜索到的点为 距离最短的 点
BFS 稳定 DFS 不稳定
回溯 . 剪枝
算法思路比较奇怪 或 对空间要求比较高: DFS 求最短路 : BFS
例题一 :
全排列问题 :
给定一个整数 n , 将数字 1 ~ n 排成一排 , 将会有很多种排列方法 .
现在 , 请你按照字典序将所有的排列方法输出 .
sample input :
3
**sample output : **
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
注 : DFS最重要的就是顺序 – 我们要用什么样的顺序来把某一道题目的所有方案遍历一遍
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EElE7OOY-1601088852850)(…/…/…/…/tygatyga/Typora/images/image-20200912190127968.png)]
代码如下 :
#includeusing namespace std;const int N = 10 ;int n ;int path[N] ; bool st[N] ;void dfs(int u){ // 如果当前搜索到的层数是全排列的位数 , 则打印输出 if(u == n) { for(int i = 0;i < n;i ++ ) printf("%d ",path[i]) ; puts("") ; return ; } for (int i = 1;i <= n;i ++ ) { if(!st[i]) { path[u] = i ; st[i] = true ; dfs(u + 1) ; st[i] = false ; // 回溯 , 恢复状态 } }}int main(){ cin >> n ; dfs(0) ; return 0 ;}
**注意的地方 : ** 需加bool数组记录当前访问的结点是否被访问过 , 在回溯的时候应注意恢复状态
八( n )皇后问题 :
将n个皇后放在 n*n 的国际象棋棋盘上 , 使得皇后不能相互攻击到 , 即任意两个
皇后都不能处于同一行 , 同一列上 或者 同一斜线上 给定整数 n 输出所有的满足条件的棋子摆法剪枝操作
最坏时间复杂度 : O( 2n2 )
思路 :
顺序 : 从第一行开始看 , 枚举每一行 , 看这个皇后能放到哪个位置上去 , 类似于全排列 , 先把 n 的全排列求出来 , 再判断其是否合法 , 也可以边做边判断 , 在枚举的时候就进行判断 , 在搜索的时候如果产生冲突 , 则立刻停止搜索并回溯 , 继续搜索其他的结点 , 这个过程就叫做剪枝
通过剪枝实现 :
代码如下 :
// 将n个皇后放在 n*n 的国际象棋棋盘上 , 使得皇后不能相互攻击到 , 即任意两个// 皇后都不能处于同一行 , 同一列上 或者 同一斜线上// 给定整数 n 输出所有的满足条件的棋子摆法#includeusing namespace std;const int N = 100 + 5 ;char g[N][N] ; bool col[N] , dg[N] , udg[N] ;int n ;void dfs(int u){ if(u == n) { for(int i = 0;i < n;i ++ ) puts(g[i]) ; puts("") ; return ; } for(int i = 0;i < n;i ++ ) { // 推导 : 斜线公式 : y = x + b , y = -x + b ; // b = y - x , b = y + x ; // 注意 : 这里为防止 y - x 为负数导致数组下标越界 , 所以加上一个偏移量 n // 剪枝操作 : if(!col[i] && !dg[n - u + i] && !udg[u + i]) { g[u][i] = 'Q' ; col[i] = dg[n - u + i] = udg[u + i] = true ; dfs(u + 1) ; col[i] = dg[n - u + i] = udg[u + i] = false ; g[u][i] = '.' ; } }}int main(){ cin >> n ; for(int i = 0 ;i < n;i ++ ) for(int j = 0;j < n;j ++ ) g[i][j] = '.' ; dfs(0) ; return 0 ;}
法二 :
dfs原始做法 : 一个一个格子搜索 , 每次判断是否符合条件
最坏时间复杂度 O( n! )
代码如下 :
// n皇后法二(dfs原始方法) : 一个格子一个格子搜 每次搜的时候进行判断是否成立#includeusing namespace std;const int N = 100 + 5 ;char g[N][N] ; int n ; bool row[N] , col[N] , dg[N] , udg[N] ;// s 为当前以及放置了的皇后的个数void dfs(int x , int y , int s){ // 如果当前行搜索完毕 , 则继续搜索下一行 if(y == n) y = 0 , x ++ ; if(x == n) { if(s == n) { for(int i = 0;i < n;i ++ ) puts(g[i]) ; puts("") ; } return ; } // 不放皇后 : dfs(x , y + 1,s) ; // 放皇后 : if(!row[x] && !col[y] && !dg[n - x + y] && !udg[x + y]) { g[x][y] = 'Q' ; row[x] = col[y] = dg[n - x + y] = udg[x + y] = true ; dfs(x , y + 1 , s + 1) ; // 恢复现场 row[x] = col[y] = dg[n - x + y] = udg[x + y] = false ; g[x][y] = '.' ; }}int main(){ cin >> n ; for(int i = 0;i < n ;i ++ ) for(int j = 0;j < n ;j ++ ) g[i][j] = '.' ; dfs(0,0,0) ; return 0 ;}
第一种搜索顺序更快
dfs问题没有模版 , 重要的是抓住搜索的顺序 , 和剪枝操作 .
**BFS : **
经典问题 :
给定一个 n*n 的二维迷宫, 用数组来表示 , 数组中只包含 0 . 1 , 其中 0 表示可以走的路 , 1 表示不可以走的路 , 最初 , 有一个人位于左上角(1 , 1)处 , 已知该人每次可向上 . 下 . 左 . 右 任意一个方向移动一个位置 , 求最少的步数到 点(n,m)
注意 : 只有当所有边的权重都相等的时候 , 才能使用BFS进行求解 , 否则只能通过最短路算法来进行求解 .
DP问题是一类特殊的最短路问题 , 没有环
**边权都为 1 的时候 , 才能用 BFS **
基本框架 :
过程 : 初始状态放到队列里面去
while ( 队列不空 )
{
取队头 , 扩展队头
}
代码如下( 人工模拟队列版 ) :
#include#include #include #include using namespace std ;typedef pair PII ;const int N = 110 ;int g[N][N] ; int d[N][N] ; int n , m ; PII q[N * N] ;int bfs(){ // 人工模拟队列 : int hh = 0 , tt = 0 ; q[0] = { 0 , 0} ; memset(d,-1,sizeof d) ; d[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 ++ ) { // 往上下左右四个方向进行搜索 , 看是否能走通 int x = t.first + dx[i] , y = t.second + dy[i] ; if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) { d[x][y] = d[t.first][t.second] + 1 ; q[++ tt] = { x,y} ; // 如果搜索到的点可以走, 则将其入队 } } } return d[n - 1][m - 1] ;}int main(){ scanf("%d%d",&n,&m) ; for(int i = 0;i < n;i ++ ) for(int j = 0;j < m;j ++ ) { scanf("%d",&g[i][j]) ; } cout << bfs() << endl ; return 0 ;}
STL版本 :
#include#include #include #include using namespace std ;struct node{ int x, y, steps ;};const int N = 110 ;int g[N][N] ; bool book[N][N] ; int n , m ;void bfs(){ queue q ; node n1 ; n1.x = n1.y = n1.steps = 0 ; q.push(n1) ; memset(book,false,sizeof book) ; int dir[4][2] = { -1,0, 1,0, 0,1, 0,-1} ; while (!q.empty()) { node t = q.front() ; q.pop() ; if(t.x == n - 1 && t.y == m - 1) { cout << t.steps << endl ; return ; } for(int i = 0;i < 4;i ++ ) { int x = t.x + dir[i][0] , y = t.y + dir[i][1] ; if(x < n && x >= 0 && y < m && y >= 0 && g[x][y] == 0 && !book[x][y]) { node temp = t ; temp.x = x , temp.y = y ; temp.steps++ ; q.push(temp) ; } } }}int main(){ cin >> n >> m ; for(int i = 0;i < n;i ++ ) for(int j = 0;j < m;j ++ ) scanf("%d",&g[i][j]) ; bfs() ; return 0 ;}
// 需要两个状态 : now 和 next
树与图的遍历 . 拓扑排序
1.树与图的存储
树是一种特殊的图 , 无环 , 连通
无向图又是一种 特殊的有向图 , 因此这里只考虑有向图
有向图的存储 :
- 邻接矩阵 二维数组g[a] [b] 比较浪费空间 , 使用较少 , 一般用来存稠密图 n^2
- 邻接表 n个点 --> n个单链表 头插法 .
vector 效率比 数组 低
树的重心 :
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CdRwZqFd-1601088852853)(…/…/…/…/tygatyga/Typora/images/image-20200923192013113.png)]
// Problem Description :
// 给定一棵树 , 树中包含 n 个结点(编号 1 ~ n) 和 n - 1 条无向边 , // 找到树的重心 , 并且输出将树的重心删除后 , 剩余各个连通块的最大值 // 重心 : 树中的一个结点 , 如果这个点删除后 , 剩余各个连通块中点数的最大值最小 ,bfs 和 dfs 的时间复杂度都是 O(n + m)
代码如下 :
#include#include #include using namespace std ;const int N = 100010 , M = N << 1 ;int h[N] , e[N] , ne[N] , idx ; int n ; int ans = N ;bool st[N] ;void add(int a , int b){ e[idx] = b ; ne[idx] = h[a] ; h[a] = idx ++ ;}int dfs(int u){ st[u] = true ; // sum 表示当前子树的总结点数 , res 表示删去当前结点后树中连通块的最大值 . int sum = 1 , res = 0 ; for (int i = h[u] ; i != -1;i = ne[i]) { int j = ne[i] ; if(!st[j]) { int s = dfs(j) ; res = max(res,s) ; // 第一次比较 sum += s ; } } res = max(res , n - sum) ; // 第二次比较 ans = min(res,ans) ; // 答案比较 return sum ;}int main(){ memset(h,-1,sizeof h) ; cin >> n ; for(int i = 0;i < n - 1;i ++ ) { int a , b ; cin >> a >> b ; add(a,b) ; add(b,a) ; } dfs(1) ; cout << ans << endl ; return 0 ;}
2.树与图的深度优先遍历
3.树与图的宽度优先遍历
EX : 图中点的层次 :
给定一个 n 个点 m条边的有向图 , 图中可能存在重边 和 自环 .
所有边的长度都是 1 , 点的编号为 1 ~ n
求出 1 号点到 n号点的最短距离 , 如果 从 1 号点无法走到n号点 , 输出 -1 ;
框架 :
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gTLE4R4p-1601088852855)(…/…/…/…/tygatyga/Typora/images/image-20200924190433283.png)]
代码如下 :
#include#include #include using namespace std ;const int N = 100010 ;int h[N] , e[N] , ne[N] , idx ; int n , m ;int q[N] , d[N] ;void add(int a ,int b){ e[idx] = b ; ne[idx] = h[a] ; h[a] = idx ++ ;}int bfs(){ int hh = 0 , tt = 0 ; q[0] = 1 ; memset(d,-1,sizeof h) ; d[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(){ cin >> n >> m ; memset(h,-1,sizeof h) ; for(int i = 0;i < m;i ++ ) { int a , b ; cin >> a >> b ; add(a,b) ; } cout << bfs() << endl ; return 0 ;}
4.拓扑排序
有向图的拓扑序列 (图的宽度优先遍历 bfs)
给定一个 n 个点 m 条边的有向图 , 图中可能存在重边和自环 ,
请输出任意一个该有向图的拓扑序列 , 如果不存在 , 则输出 - 1.
有向无环图 --> 一定存在一个拓扑序列
有向无环图 --> 拓扑图
步骤 :
所有入度为 0 的点 --> 入队
while queue 不空
{
t <-- 队头 ; 枚举 t 的所有出边 ; t – > j ;
删掉 t --> j ; j 的入度 -1 ;
if j 的入度为 0 ; j 入队 ;
}
不断找入度为 0 的点 , 将其突破 .
代码如下 :
#include#include #include using namespace std ;const int N = 100010 ;int h[N] , e[N] , ne[N] , idx ; int n , m ;int q[N] , d[N] ;void add(int a,int b){ e[idx] = b ; ne[idx] = h[a] ; h[a] = idx ++ ;}bool topsort(){ // 用数组模拟队列 , 比 STL 要快的多 int hh = 0 , tt = -1 ; for(int i = 1;i <= n;i ++ ) { if(!d[i]) q[++ tt] = i ; } while (hh <= tt) { int t = q[hh ++] ; for(int i = h[t] ; i != -1;i = ne[i]) { int j = e[i] ; d[j] -- ; if(!d[j]) q[++ tt] = j ; } } return tt == n - 1 ;}int main(){ cin >> n >> m ; memset(h,-1,sizeof h) ; for(int i = 0;i < m;i ++ ) { int a , b ; cin >> a >> b ; add(a,b) ; d[b] ++ ; } if(topsort()) { for(int i = 0;i < n;i ++ ) printf("%d ", q[i]) ; puts("") ; } else puts("-1") ; return 0 ;}
转载地址:https://blog.csdn.net/weixin_45877540/article/details/108552555 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!