图 . 树 . bfs . dfs .
发布日期:2022-02-24 01:06:48 浏览次数:12 分类:技术文章

本文共 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)]

代码如下 :

#include 
using 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 的全排列求出来 , 再判断其是否合法 , 也可以边做边判断 , 在枚举的时候就进行判断 , 在搜索的时候如果产生冲突 , 则立刻停止搜索并回溯 , 继续搜索其他的结点 , 这个过程就叫做剪枝

image-20200914184825946

通过剪枝实现 :

代码如下 :

// 将n个皇后放在 n*n 的国际象棋棋盘上 , 使得皇后不能相互攻击到 , 即任意两个// 皇后都不能处于同一行 , 同一列上 或者 同一斜线上// 给定整数 n 输出所有的满足条件的棋子摆法#include 
using 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原始方法) : 一个格子一个格子搜 每次搜的时候进行判断是否成立#include 
using 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.树与图的存储

树是一种特殊的图 , 无环 , 连通

无向图又是一种 特殊的有向图 , 因此这里只考虑有向图

有向图的存储 :

  1. 邻接矩阵 二维数组g[a] [b] 比较浪费空间 , 使用较少 , 一般用来存稠密图 n^2
  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条边的有向图 , 图中可能存在重边 和 自环 .

image-20200924190001316

所有边的长度都是 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:各种最短路径算法
下一篇:二分图与最小生成树

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月16日 00时57分44秒