您现在的位置是：首页 >技术教程 >day08.搜索与图论--1（bfs+dfs+拓扑）网站首页技术教程

day08.搜索与图论--1（bfs+dfs+拓扑）

Aurora_eye 2025-08-24 00:01:07
简介day08.搜索与图论--1（bfs+dfs+拓扑）

在这里插入图片描述

一、深度优先搜索（DFS）

关键： 回溯，剪枝

（1）题目：全排列问题 (AcWing 842.排列数字)

在这里插入图片描述

  1. 定义一个数组path[N] 来保存当前的路径/模拟DFS的过程
  2. 确定输出条件：当这个数组数字填满的时候，此时把当前的排列数字输出出来。
  3. 确定单层递归逻辑：当前数组位置为空，还可以填数。
  4. 回溯：恢复现场
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

const int N = 10;
int n;
int path[N];   // 保存路径
bool st[N];    //数字使用情况，true表示已使用

void dfs(int u) { //u表示层数
	if (u == n) {
		for (int i = 0; i < n; i++)
			cout << path[i];
		cout << " ";
		cout << endl;
		return;
	}

	for (int i = 1; i <= n; i++)
		if (!st[i]) { // 数字i未使用
			path[u] = i;
			st[i] = true;
			dfs(u + 1); //继续填充下一个数
			st[i] = false; // 回溯，恢复原状
		}
}

int main() {
	cin >> n;
	dfs(0);
	return 0;
}

（2）题目： AcWing 843.n-皇后问题

在这里插入图片描述
关于对角线：
row表示行，col表示列。代码中坐标用（x，y）表示，x为行，y为列。
左上方向为主对角线，右上方向为副对角线。
在这里插入图片描述

① 思路一：原始方法

DFS按每个元素枚举 时间复杂度O(2的n2次幂)，因为每个位置都有两种情况，总共有 n^2 个位置

  1. 确定参数。
  2. 确定输出条件：已遍历至最后一行，且皇后已经放置完毕。则输出
  3. 确定单层递归条件：① 皇后能放在这格。② 不能放，移至改行的下一个格子。
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
// 对于一个 n * n 的矩阵，通常有 2n - 1 条对角线、反对角线
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) { //xy为坐标(x,y),s为皇后放置个数
	if (y == n) {  //当皇后走到了一行的尽头
		y = 0;     //则，转到下一行的开头
		x++;
	}
	if (x == n) {  // 遍历到最后一行
		if (s == n) { // 所有皇后已经放置完毕
			for (int i = 0; i < n; i++) //puts输出每一行,并自动换行
				puts(g[i]);
			puts("");  //打印一个空行，用于分隔不同解
		}
		return;
	}

	// ① 判断皇后能否放在这格
	if (!row[x] && !col[y] && !dg[x - y + n] && !udg[x+y]) {
		g[x][y] = 'Q';   //放置皇后
		row[x] = col[y] = dg[x - y + n] = udg[x + y] = true;  // 更新状态
		dfs(x, y + 1, s + 1); //放置皇后，并找下一层的
		row[x] = col[y] = dg[x - y + n] = udg[x + y] = false; //回溯，恢复现场
		g[x][y] = '.';
	}
    // ② 不放皇后,并且访问右节点
	dfs(x, y + 1, s);
}

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;
}

② 思路二（剪枝法，高效）

  1. 按行遍历。结束条件：遍历到最后一行。
  2. 单层递归逻辑：遍历该行的每一列，利用col，dg，udg验证合法性。
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
// 对于一个 n * n 的矩阵，通常有 2n - 1 条对角线、反对角线
const int N = 20;

int n;
char g[N][N];   // 存储棋盘
bool col[N], dg[N], udg[N]; // 列、对角线、反对角线

void dfs(int x) {
	if (x == n) {
		for (int i = 0; i < n; i++)
			puts(g[i]);
		puts("");
		return;
	}

	//按行枚举 因为每一行都需要放皇后 相当于剪枝了
	// 判断皇后能否放在这格
	for (int y = 0; y < n; y++) {
		if (!col[y] && !dg[x - y + n] && !udg[x + y]) {
			g[x][y] = 'Q';
			col[y] = dg[x - y + n] = udg[x + y] = true;
			dfs(x + 1);    // 该层放置完毕，继续下一层
			col[y] = dg[x - y + n] = 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);          //从第一行开始找

	return 0;
}

PS： 可供参考：DFS解题思路

//参数用来表示当前状态; 
//返回值是我们dfs完成之后想要获取的数据，如果不需要返回值或者通过全局变量来记录状态的话ReturnType可以为void
//函数名可以换成更有意义的名字
ReturnType dfs(param1,params2,...) 
{
     
    if(终点状态 || 非法状态 || 需要剪枝)  
    {
     
        ... //退出前处理
        return;  
    }  
    for(每一个当前状态相关的下一个状态)  
    {
     
        if(该状态合法 && 该状态未被标记)  
        {
     
            ...; // 当前状态应该做的处理（遍历前需要的处理）(根据实际情况来判断是否需要)
            标记当前状态；  
            dfs（）；  
            ...; // 当前状态应该做的处理（遍历后需要的处理）(根据实际情况来判断是否需要)
            (还原标记); //可选操作, 如果加上这句就是"回溯法"  
        }  
 
    }  
}

二、宽度优先搜索（BFS）-----最短路

可以用bfs求最短路的前提是，权值相等。

（1）题目：AcWing 844.走迷宫

在这里插入图片描述

  • 模拟队列法
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

const int N = 110;
typedef pair<int, int> PII;  // pair便于存储路径

int n, m;
int g[N][N];   // 存储迷宫地图
int d[N][N];   // 存储当前点到起点的最短距离
int prev[N][N];
PII q[N * N];  // 模拟队列

int bfs() {
	// 模拟队列
	int hh = 0, tt = -1;
	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];
		hh++;
		// 检查四个方向是否合法，若合法则可走，将位置加进队列
		for (int i = 0; i < 4; i++) {
			// 移动
			int x = t.first + dx[i];
			int 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; // 更新距离数组
				prev[x][y] = t;   // !记录当前位置是从哪个位置过来的
				q[++tt] = {x, y}; // 将 当前点 加入队列
			}
		}
	}

	//!输出走出迷宫的路径
	int x = n - 1, y = m - 1; // 从终点倒退来路
	while (x || y) {  // (x,y)=(0,0)时退出
		cout << x << ' ' << y << endl;
		auto t = prev[x][y]; // 找来路
		x = t.first, y = t.second;
	}

	return d[n - 1][m - 1];
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> g[i][j];

	cout << bfs() << endl;
}
  • 非模拟queue
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

const int N = 110;
typedef pair<int, int> PII;  // pair便于存储路径

int n, m;
int g[N][N];   // 存储迷宫地图
int d[N][N];   // 存储当前点到起点的最短距离
int prev[N][N];

int bfs() {
	queue<PII> q;
	q.push({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 (!q.empty()) {
		auto t = q.front();
		q.pop();

		// 检查四个方向是否合法，若合法则可走，将位置加进队列
		for (int i = 0; i < 4; i++) {
			// 移动
			int x = t.first + dx[i];
			int 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; // 更新距离数组
				prev[x][y] = t;   // !记录当前位置是从哪个位置过来的
				q.push({x, y}); // 将 当前点 加入队列
			}
		}
	}

	//!输出走出迷宫的路径
	int x = n - 1, y = m - 1; // 从终点倒退来路
	while (x || y) {  // (x,y)=(0,0)时退出
		cout << x << ' ' << y << endl;
		auto t = prev[x][y]; // 找来路
		x = t.first, y = t.second;
	}

	return d[n - 1][m - 1];
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> g[i][j];

	cout << bfs() << endl;
	return 0;
}

（2）题目：AcWing 845. 八数码

三、树与图的存储

树是一种特殊的图（无环连通图）。
对图而言，无向图又可以表示为a—>b，b—>a均可达的有向图。
换言之，只需要掌握有向图的存储即可。有向图的存储方式有两种，邻接矩阵和邻接表

  • 邻接矩阵

是一个二维数组，g[a][b]存储的是a —> b的信息，若边有权重，则g[a][b]存的就是权重；若没有权重，g[a][b]存的就是一个bool值。邻接矩阵不能存储重边，只能保留1条。

  • 邻接表

是给每一个结点都开一个单链表，每个单链表存的就是这个点可以走到哪些点。若一个图中有n个结点，则邻接表中就有n个单链表，在前面学习单链表时，我们给head初始化为-1，现在就给h都初始化为-1

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
 
const int N = 1e5 + 10, M = 2 * N; // 因为是有向图，所以e和ne需要开2倍的N
int h[N], e[M], ne[M], idx; // h数组存的是n个链表的 链表头
 
void add(int a, int b) // 插入边a -> b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
 
int main()
{
    memset(h, -1, sizeof(h)); // 将链表头都初始化为-1，表示每一个链表都没有元素
    return 0;
}

四、树与图的深度优先遍历（DFS）

无论是深度优先遍历还是广度优先遍历，每个结点都只会遍历一遍，所以在实现时，会开一个bool数组来存哪些点已经被遍历过了

题目： AcWing 846.树的重心
在这里插入图片描述

  1. 遍历每个点，依次将该点删除
  2. 计算删除该点，计算剩余的各个连通块中，结点数最多的连通块中有多少个节点。（递归）
  3. 对比 删除各个节点 所得出的最大值，选出这些最大值中的最小值。这个最小值所对应的删除节点即为树的重心。

关键： 通过 递归 计算 剩下的连通块中点数的最大值。
子树节点数目①用于寻找最大res；②用于求和sum

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 2 * N;

int ans = N, n; // ans存的是最大值的最小值，也就是最终结果
int h[N], e[M], ne[M], idx = 0; // 邻接表
bool st[N];   // 各节点的访问情况

void add(int a, int b) {
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx;
	idx++;
}

// 在以u为根的子树中 结点的数量
int dfs(int u) {
	st[u] = true; // 标记已经访问

	// sum用来记录当前子树点的个数，并且当前所在的这个结点也算1个，所以sum从1开始
	// res记录 把当前结点删除后，剩下连通块中点的最大值
	int sum = 1, res = 0;
	for (int i = h[u]; i != -1; i = ne[i]) { // 遍历当前结点的所有孩子
		int j = e[i];
		if (!st[j]) {
			int childsum = dfs(j);  // 用dfs 递归 算该树的子树中的结点数
			res = max(res, childsum);
			sum += childsum;
		}
	}

	// 循环中res只是与当前结点的子树相比较，结点删除后，上面的一大块也是连通块，所以也要与之比较
	res = max(res, n - sum);

	ans = min(ans, res);

	return sum;
}

int main() {
	cin >> n;  // 输入结点数
	memset(h, -1, sizeof(h));

	for (int i = 0; i < n - 1; i++) { // n-1是因为，n个结点只有n-1条边
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}

	dfs(1);

	cout << ans << endl;
	return 0;
}

五、树与图的宽度优先遍历（BFS）

题目： AcWing 847.图中点的层次
在这里插入图片描述

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 2 * N;

int n,m;
int h[N], e[M], ne[M], idx = 0; // 邻接表
int d[N];

void add(int a, int b) {
	e[idx] = b;
	ne[idx] = h[a];
	ne[h[a]] = idx;
	idx++;
}


int bfs() {
	queue<int> q; 
	q.push(1);
	
	// 初始化距离数组，另一方面，距离数组也能起到bool数组的作用
	// 即如果d[i]=-1则说明未访问过。
	memset(h,-1,sizeof(d));
	d[1]=0;
	
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];
			if(d[j]==-1){   // 未访问过
				d[j]=d[t]+1; // 距离+1
				q.push(j);
			}
		}
	}
	return d[n];		
}

int main() {
	cin >> n >> m;  // 输入结点数
	memset(h, -1, sizeof(h));

	for (int i = 0; i < m; i++) { // n-1是因为，n个结点只有n-1条边
		int a, b;
		cin >> a >> b;
		add(a, b);
	}

	cout << bfs() <<endl;
	return 0;
}

六、拓扑排序（针对有向图）

  1. 若一个图中存在环，则这个环上的点一定不会入队列的。
  2. 一个无环图，一定存在一个入度为0的点。
  3. 拓扑序列不唯一。

题目： AcWing 848.有向图的拓扑序列
在这里插入图片描述

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx = 0; // 邻接表
int q[N], d[N];  //存储各结点的入度

void add(int a, int b) {
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx;
	idx++;
}

bool topsort() {
	int hh = 0, tt = -1;
	for (int i = 1; i <= n; i++) {
		if (d[i] == 0)
			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]--;  // 入度-1
			if (d[j] == 0) {
				q[++tt] = j;
			}
		}
	}
	// 若全部点都放进了队列，则这个图是有拓扑序列的
	return tt == n - 1;   //所有点都入过队列了。
}

int main() {
	cin >> n >> m;  // 输入结点数

	memset(h, -1, sizeof(h));
	//memset(h, 0, sizeof(d));

	for (int i = 0; i < m ; i++) { // m条边
		int a, b;
		cin >> a >> b;
		add(a, b);
		d[b]++;  // b结点 入度加1
	}

	if (topsort()) { // 存在拓扑序列，则输出 n个点的入队顺序
		for (int i = 0; i < n; i++)
			printf("%d ", q[i]);
		puts("");
	} else  //不存在拓扑序列
		puts("-1");

	return 0;
}
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐