图论 - DFS深度优先遍历、BFS广度优先遍历、拓扑排序
前言
本篇博客将介绍DFS-深度优先遍历、BFS-广度优先遍历和拓扑排序的常见题型(模板题及其扩展)。DFS和BFS是遍历图的两种方法,其中BFS多用于求最短路问题,在不要求最短时多用DFS,因为DFS的复杂度更低。而拓扑排序是图论中一种特殊的问题,用于求图中是否存在回路。
Part 1:DFS(深度优先遍历)
一、排列数字
1.题目描述
给定一个整数 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
2.算法
- 假设有 3 个空位,从前往后填数字,每次填一个位置,填的数字不能和前面一样。
- 最开始的时候,三个空位都是空的: __。首先填写第一个空位,第一个空位可以填 1,填写后为:1。填好第一个空位,填第二个空位,第二个空位可以填 2,填写后为:1 2 __。填好第二个空位,填第三个空位,第三个空位可以填 3,填写后为: 1 2 3。这时候,空位填完,无法继续填数,所以这是一种方案,输出。
- 然后往后退一步,退到了状态:1 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3 ,没有其他数字可以填。因此再往后退一步,退到了状态:1 。第二个空位上除了填过的 2,还可以填 3。第二个空位上填写 3,填写后为:1 3 __。填好第二个空位,填第三个空位,第三个空位可以填 2,填写后为: 1 3 2。这时候,空位填完,无法继续填数,所以这是一种方案,输出。
- 如此反复
#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{
if(u > n)//数字填完了,输出
{
for(int i = 1; i <= n; i++)//输出方案
cout << path[i] << " ";
cout << endl;
}
for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n
{
if(!state[i])//如果数字 i 没有被用过
{
path[u] = i;//放入空位
state[i] = 1;//数字被用,修改状态
dfs(u + 1);//填下一个位
state[i] = 0;//回溯,取出 i
}
}
}
int main()
{
cin >> n;
dfs(1);
}
二、n皇后问题
1.问题描述
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n,请你输出所有的满足条件的棋子摆法。
输入格式
共一行,包含整数 n。
输出格式
每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。
其中 .
表示某一个位置的方格状态为空,Q
表示某一个位置的方格上摆着皇后。
每个方案输出完成后,输出一个空行。
注意:行末不能有多余空格。
输出方案的顺序任意,只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例
4
输出样例
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
2.算法
- 按行枚举,回溯剪枝
#include <iostream>
using namespace std;
const int N = 20;
// bool数组用来判断搜索的下一个位置是否可行
// col列,dg对角线,udg反对角线
// g[N][N]用来存路径
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u) {
// u == n 表示已经搜了n行,故输出这条路径
if (u == n) {
for (int i = 0; i < n; i ++ ) puts(g[i]); // 等价于cout << g[i] << endl;
puts(""); // 换行
return;
}
// 枚举u这一行,搜索合法的列
int x = u;
for (int y = 0; y < n; y ++ )
// 剪枝(对于不满足要求的点,不再继续往下搜索)
if (col[y] == false && dg[y - x + n] == false && udg[y + x] == false) {
col[y] = dg[y - x + n] = udg[y + x] = true;
g[x][y] = 'Q';
dfs(x + 1);
g[x][y] = '.'; // 恢复现场
col[y] = dg[y - x + n] = udg[y + x] = false;
}
}
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;
}
三、树的重心
1.问题描述
给定一颗树,树中包含 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
2.算法
- 本题的本质是树的dfs, 每次dfs可以确定以u为重心的最大连通块的节点数,并且更新一下ans
- 也就是说,dfs并不直接返回答案,而是在每次更新中迭代一次答案
- 用邻接表存储
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图,所以每个节点至多对应2n-2条边
int h[N]; //邻接表存储树,有n个节点,所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入,n个节点
int ans = N; //表示重心的所有的子树中,最大的子树的结点数目
bool st[N]; //记录节点是否被访问过,访问过则标记为true
//a所对应的单链表中插入b a作为根
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
//返回以u为根的子树中节点的个数,包括u节点
int dfs(int u) {
int res = 0; //存储 删掉某个节点之后,最大的连通子图节点数
st[u] = true; //标记访问过u节点
int sum = 1; //存储 以u为根的树 的节点数, 包括u,如图中的4号节点
//访问u的每个子节点
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
//因为每个节点的编号都是不一样的,所以 用编号为下标 来标记是否被访问过
if (!st[j]) {
int s = dfs(j); // u节点的单棵子树节点数 如图中的size值
res = max(res, s); // 记录最大联通子图的节点数
sum += s; //以j为根的树 的节点数
}
}
//n-sum 如图中的n-size值,不包括根节点4;
res = max(res, n - sum); // 选择u节点为重心,最大的 连通子图节点数
ans = min(res, ans); //遍历过的假设重心中,最小的最大联通子图的 节点数
return sum;
}
int main() {
memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
cin >> n; //表示树的结点数
// 题目接下来会输入,n-1行数据,
// 树中是不存在环的,对于有n个节点的树,必定是n-1条边
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a); //无向图
}
dfs(1); //可以任意选定一个节点开始 u<=n
cout << ans << endl;
return 0;
}
Part 2:BFS(广度优先遍历)
一、走迷宫
1.问题描述
给定一个 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
2.算法
- 从起点开始,往前走第一步,记录下所有第一步能走到的点,然后从所第一步能走到的点开始,往前走第二步,记录下所有第二步能走到的点,重复下去,直到走到终点。输出步数即可
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
int g[N][N], d[N][N];//g存储地图,d存储距离
int bfs()
{
queue<PII> q;
memset(d, -1, sizeof d); //距离初始化
d[0][0] = 0;
q.push({0, 0});
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
//BFS宽度优先遍历
while (q.size())
{
auto t = q.front();
q.pop();
//上下左右四种走法
for (int i = 0; i < 4; i ++ )
{
int x = t.first + dx[i], y = t.second + dy[i];
//未超过边界(x、y的限制),且此处可走(g是0),且未走过(d是-1)
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.push({x, y});
}
}
}
return d[n - 1][m - 1];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin >> g[i][j];
cout << bfs() << endl;
return 0;
}
二、八数码
1.题目描述
在一个 3×3 的网格中,1∼8 这 8 个数字和一个 x
恰好不重不漏地分布在这 3×3 的网格中。
例如:
1 2 3
x 4 6
7 5 8
在游戏过程中,可以把 x
与其上、下、左、右四个方向之一的数字交换(如果存在)。
我们的目的是通过交换,使得网格变为如下排列(称为正确排列):
1 2 3
4 5 6
7 8 x
例如,示例中图形就可以通过让 x
先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下:
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
现在,给你一个初始网格,请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行,将 3×3 的初始网格描绘出来。
例如,如果初始网格如下所示:
1 2 3
x 4 6
7 5 8
则输入为:1 2 3 x 4 6 7 5 8
输出格式
输出占一行,包含一个整数,表示最少交换次数。
如果不存在解决方案,则输出 −1。
输入样例
2 3 4 1 5 x 7 6 8
输出样例
19
2.算法
-
将 “3*3矩阵” 转化为 “字符串”
-
二维矩阵下标转化一维字符串下标
-
最终状态则是:“12345678x”
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
int bfs(string start)
{
//定义目标状态
string end = "12345678x";
//定义队列和dist数组
queue<string> q;//直接存转化后的字符串
unordered_map<string, int> d;//将字符串和数字联系在一起,字符串表示状态,数字表示距离
//初始化队列和dist数组
q.push(start);
d[start] = 0;
//转移方式
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
while(q.size())
{
auto t = q.front();
q.pop();
//记录当前状态的距离,如果是最终状态则返回距离
int distance = d[t];
if(t == end) return distance;
//查询x在字符串中的下标,然后转换为在矩阵中的坐标
int k = t.find('x');
int x = k / 3, y = k % 3;
for(int i = 0; i < 4; i++)
{
//求转移后x的坐标
int a = x + dx[i], b = y + dy[i];
//当前坐标没有越界
if(a >= 0 && a < 3 && b >= 0 && b < 3)
{
//转移x
swap(t[k], t[a * 3 + b]);
//如果当前状态是第一次遍历,记录距离,入队
if(!d.count(t))
{
d[t] = distance + 1;
q.push(t);
}
//还原状态,为下一种转换情况做准备
swap(t[k], t[a * 3 + b]);
}
}
}
//无法转换到目标状态,返回-1
return -1;
}
int main()
{
string c, start;
//输入起始状态
for(int i = 0; i < 9; i++)
{
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}
三、图中点的层次
1.题目描述
给定一个 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
2.算法
- 邻接表存储的BFS,思路与前面完全一致
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int h[N],ne[N], e[N], idx;//邻接表数据结构
int dist[N];//存储距离
int st[N];//标记点是否走到过
int n, m;
void add(int a, int b)//邻接表存储图
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs()
{
memset(dist, 0x3f, sizeof(dist));//初始都没有走到过,距离无穷大
dist[1] = 0;//从1号节点开始,距离为0
queue<int> q;//队列
q.push(1);//1号节点入队列
st[1] = 1;//1到1的距离为0,已经求出
while(q.size())//对列非空,就一直往后搜索
{
int t = q.front();//队头出队,找该点能到的点
q.pop();
for(int i = h[t]; i != -1; i = ne[i])//遍历所有t节点能到的点,i为节点索引
{
int j = e[i];//通过索引i得到t能到的节点编号
if(!st[j])//如果没有遍历过
{
dist[j] = dist[t] + 1;//距离为t号节点的距离+1
q.push(j);//节点入队
st[j] = 1;//入队后标记,已经遍历过了
}
}
}
}
int main()
{
cin >> n >>m;
memset(h, -1, sizeof h);//初始化,所有节点没有后继,后继都是-1
for(int i = 0; i < m; i++)//读入所有边
{
int a, b;
cin >> a >> b;
add(a, b);//加入邻接表
}
bfs();//广度优先遍历
cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]);//如果到n号节点的距离不是无穷大,输出距离,如果是无穷大,输出-1.
return 0;
}
Part 3:拓扑排序
一、有向图的拓扑序列
1.题目描述
给定一个 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
2.算法
- 什么是拓扑排序?一个有向图,如果图中有入度为 0 的点,就把这个点删掉,同时也删掉这个点所连的边。一直进行此处理,如果所有点都能被删掉,则这个图可以进行拓扑排序。
- 首先记录各个点的入度
- 然后将入度为 0 的点放入队列
- 将队列里的点依次出队列,然后找出所有出队列这个点发出的边,删除边,同事边的另一侧的点的入度 -1。
- 如果所有点都进过队列,则可以拓扑排序,输出所有顶点。否则输出-1,代表不可以进行拓扑排序。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int q[N], hh = 0, tt = -1;//队列保存入度为0的点,也就是能够输出的点,
int n, m;//保存图的点数和边数
int d[N];保存各个点的入度
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void topsort(){
for(int i = 1; i <= n; i++){//遍历一遍顶点的入度。
if(d[i] == 0)//如果入度为 0, 则可以入队列
q[++tt] = i;
}
while(tt >= hh){//循环处理队列中点的
int a = q[hh++];
for(int i = h[a]; i != -1; i = ne[i]){//循环删除 a 发出的边
int b = e[i];//a 有一条边指向b
d[b]--;//删除边后,b的入度减1
if(d[b] == 0)//如果b的入度减为 0,则 b 可以输出,入队列
q[++tt] = b;
}
}
if(tt == n - 1){//如果队列中的点的个数与图中点的个数相同,则可以进行拓扑排序
for(int i = 0; i < n; i++){//队列中保存了所有入度为0的点,依次输出
cout << q[i] << " ";
}
}
else//如果队列中的点的个数与图中点的个数不相同,则可以进行拓扑排序
cout << -1;//输出-1,代表错误
}
int main(){
cin >> n >> m;//保存点的个数和边的个数
memset(h, -1, sizeof h);//初始化邻接矩阵
while (m -- ){//依次读入边
int a, b;
cin >> a >> b;
d[b]++;//顶点b的入度+1
add(a, b);//添加到邻接矩阵
}
topsort();//进行拓扑排序
return 0;
}
原文地址:https://blog.csdn.net/2203_75327677/article/details/136410998
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!