图论 – DFS深度优先遍历、BFS广度优先遍历、拓扑排序

文章目录

• 前言
• Part 1：DFS（深度优先遍历）
• • 一、排列数字
  • • 1.题目描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例
      • 输出样例
    • 2.算法
  • 二、n皇后问题
  • • 1.问题描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例
      • 输出样例
    • 2.算法
  • 三、树的重心
  • • 1.问题描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例
      • 输出样例
    • 2.算法
• Part 2：BFS（广度优先遍历）
• • 一、走迷宫
  • • 1.问题描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例
      • 输出样例
    • 2.算法
  • 二、八数码
  • • 1.题目描述
    • • 输入格式
      • 输出格式
      • 输入样例
      • 输出样例
    • 2.算法
  • 三、图中点的层次
  • • 1.题目描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例
      • 输出样例
    • 2.算法
• Part 3：拓扑排序
• • 一、有向图的拓扑序列
  • • 1.题目描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例
      • 输出样例
    • 2.算法

前言

本篇博客将介绍DFS-深度优先遍历、BFS-广度优先遍历和拓扑排序的常见题型（模板题及其扩展）。DFS和BFS是遍历图的两种方法，其中BFS多用于求最短路问题，在不要求最短时多用DFS，因为DFS的复杂度更低。而拓扑排序是图论中一种特殊的问题，用于求图中是否存在回路。

Part 1：DFS（深度优先遍历）

一、排列数字

1.题目描述

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤7

输入样例

3

输出样例

1 2 31 3 22 1 32 3 13 1 23 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。这时候，空位填完，无法继续填数，所以这是一种方案，输出。
• 如此反复

#includeusing 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;dfs(1);}

二、n皇后问题

1.问题描述

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数 n。

输出格式

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例

4

输出样例

.Q.....QQ.....Q...Q.Q......Q.Q..

2.算法

• 按行枚举，回溯剪枝

#include 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;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≤10⁵

输入样例

91 21 71 42 82 54 33 94 6

输出样例

4

2.算法

• 本题的本质是树的dfs， 每次dfs可以确定以u为重心的最大连通块的节点数，并且更新一下ans
• 也就是说，dfs并不直接返回答案，而是在每次更新中迭代一次答案
• 用邻接表存储

#include #include #include 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所对应的单链表中插入ba作为根 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 > a >> b;add(a, b), add(b, a); //无向图}dfs(1); //可以任意选定一个节点开始 u<=ncout << 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 50 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0

输出样例

8

2.算法

• 从起点开始，往前走第一步，记录下所有第一步能走到的点，然后从所第一步能走到的点开始，往前走第二步，记录下所有第二步能走到的点，重复下去，直到走到终点。输出步数即可

#include #include #include #include using namespace std;typedef pair PII;const int N = 110;int n, m;int g[N][N], d[N][N];//g存储地图，d存储距离int bfs(){queue 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 = 0 && x = 0 && y > n >> m;for (int i = 0; i < n; i ++ )for (int j = 0; j > g[i][j];cout << bfs() << endl;return 0;}

二、八数码

1.题目描述

在一个 3×3 的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。

例如：

1 2 3x 4 67 5 8

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 34 5 67 8 x

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3 1 2 3 1 2 3 1 2 3x 4 6 4 x 6 4 5 6 4 5 67 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 #include #include #include using namespace std;int bfs(string start){//定义目标状态string end = "12345678x";//定义队列和dist数组queue q;//直接存转化后的字符串unordered_map 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 = 0 && a = 0 && b < 3){//转移xswap(t[k], t[a * 3 + b]);//如果当前状态是第一次遍历，记录距离，入队if(!d.count(t)){d[t] = distance + 1;q.push(t);}//还原状态，为下一种转换情况做准备swap(t[k], t[a * 3 + b]);}}}//无法转换到目标状态，返回-1return -1;}int main(){string c, start;//输入起始状态for(int i = 0; i > 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≤10⁵

输入样例

4 51 22 33 41 31 4

输出样例

1

2.算法

• 邻接表存储的BFS，思路与前面完全一致

#include #include #include #include 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号节点开始，距离为0queue 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号节点的距离+1q.push(j);//节点入队st[j] = 1;//入队后标记，已经遍历过了}}}}int main(){cin >> n >>m;memset(h, -1, sizeof h);//初始化，所有节点没有后继，后继都是-1for(int i = 0; i > a >> b;add(a, b);//加入邻接表}bfs();//广度优先遍历cout <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 31 22 31 3
输出样例
1 2 3
2.算法
什么是拓扑排序？一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。一直进行此处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。
首先记录各个点的入度
然后将入度为 0 的点放入队列
将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同事边的另一侧的点的入度 -1。
如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序。
#include #include #include 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 = hh){//循环处理队列中点的int a = q[hh++];for(int i = h[a]; i != -1; i = ne[i]){//循环删除 a 发出的边int b = e[i];//a 有一条边指向bd[b]--;//删除边后，b的入度减1if(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 <> n >> m;//保存点的个数和边的个数memset(h, -1, sizeof h);//初始化邻接矩阵while (m -- ){//依次读入边int a, b;cin >> a >> b;d[b]++;//顶点b的入度+1add(a, b);//添加到邻接矩阵}topsort();//进行拓扑排序return 0;}