代码随想录Day50|图论Part01，leetcode题目：98. 所有可达路径

提示：DDU，供自己复习使用。欢迎大家前来讨论~

图论理论基础Part01

图的基本概念

二维坐标中，两点可以连成线，多个点连成的线就构成了图。

图的种类

连通性

在图中表示节点的连通情况，我们称之为连通性。

连通图

在无向图中，任何两个节点都是可以到达的，我们称之为连通图 ，如图：

如果有节点不能到达其他节点，则为非连通图，如图：（节点1 不能到达节点4。）

强连通图

在有向图中，任何两个节点是可以相互到达的，我们称之为 强连通图。

强连通图与无向图中的连通图的区别在于：

1. 无向图的连通性：在无向图中，如果任意两个顶点之间都存在路径（可以是单向或双向的），则该图是连通的。在无向图中，连通性不区分方向。
2. 有向图的强连通性：在有向图中，强连通性要求任意两个顶点之间都必须存在双向的路径，即从顶点A到顶点B，以及从顶点B到顶点A都存在路径。

第一个并不是强连通图，第二个是强连通图。

连通分量

在无向图中的极大连通子图称之为该图的一个连通分量。

在无向图中，连通分量是指图中最大的、所有节点都相互可达的子图，只有包含所有相互可达节点的子图才能被称为极大连通分量。

在无向图中，只有包含所有相互可达节点的极大子图才能被称为连通分量。节点3和节点4构成的子图不是连通分量，因为它们没有包含所有相互可达的节点，而节点3、节点4和节点6构成的子图才是连通分量。

强连通分量

在有向图中极大强连通子图称之为该图的强连通分量。

节点1、节点2、节点3、节点4、节点5 构成的子图是强连通分量，因为这是强连通图，也是极大图。

节点6、节点7、节点8 构成的子图 不是强连通分量，因为这不是强连通图，节点8 不能达到节点6。

节点1、节点2、节点5 构成的子图 也不是 强连通分量，因为这不是极大图。

图的构造

图的表示方法主要有以下几种：

1. 邻接矩阵：这是表示图的一种简单方式，使用二维数组来存储图中的顶点和边。在这个矩阵中，索引代表顶点，而矩阵中的元素表示顶点之间的连接关系。如果两个顶点之间有边，则相应的矩阵元素为1（或边的权重），否则为0。邻接矩阵适用于稠密图，即边的数量接近顶点数量的平方。
2. 邻接表：这是一种更节省空间的方法，特别是对于稀疏图（边的数量远小于顶点数量的平方）。在邻接表中，每个顶点对应一个列表，列表中包含与该顶点直接相连的所有顶点。这种方法可以有效地表示图的结构，并且便于遍历图中的边。
3. 朴素存储：这是一种最基本的表示方法，通常用于教学或简单的图操作。在这种方法中，图的顶点和边可能直接以数组或列表的形式存储，没有明确的结构来表示连接关系。

邻接矩阵适合于稠密图和需要频繁检查两个顶点之间是否存在边的情况，而邻接表则更适合于稀疏图和需要频繁添加或删除边的情况。

邻接矩阵

邻接矩阵是一种用二维数组表示图的方法，其中数组的元素表示顶点间的连接关系和边的权重，对于无向图，如果节点2和节点5相连，那么数组中grid[2][5]和grid[5][2]都会被设置为相同的值，表示它们之间的双向连接和边的权重。

邻接矩阵是一种图的表示方法，它使用一个二维数组来存储节点间的连接关系和边的权重。对于无向图，如果节点i和节点j相连，则数组的第i行第j列和第j行第i列都会被设置为相应的权重值。

优点：

• 表达直观，易于理解。
• 快速检查任意两个顶点之间是否存在边。

缺点：

• 在稀疏图中，会占用大量不必要的空间。
• 遍历所有边时效率低，需要检查整个矩阵。

因此，邻接矩阵适合边数较多的稠密图，但在边数较少的稀疏图中可能会导致空间和时间上的浪费。

邻接表

邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。

在邻接表中，每个顶点对应一个链表，链表中存储的是与该顶点直接相连的其他顶点的信息，包括顶点标识和边的权重（如果有的话）。

邻接表的构造如图：

这里表达的图是：

• 节点1 指向 节点3 和 节点5
• 节点2 指向 节点4、节点3、节点5
• 节点3 指向 节点4
• 节点4指向节点1

有多少边 邻接表才会申请多少个对应的链表节点。

从图中可以直观看出 使用 数组 + 链表 来表达 边的连接情况 。

邻接表的优点：

• 对于稀疏图的存储，只需要存储边，空间利用率高
• 遍历节点连接情况相对容易

缺点：

• 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
• 实现相对复杂，不易理解

图的遍历方式

深度优先搜索（DFS）和广度优先搜索（BFS）是两种基本的图遍历算法，它们也可以应用于二叉树等其他数据结构。这两种算法在图论中用于探索图中的所有顶点，确保每个顶点都被访问一次。

深度优先搜索（DFS）：

• 特点：尽可能深地搜索图的分支。
• 实现：通常使用递归或栈来实现。
• 应用：在二叉树上的递归遍历就是DFS的一种应用。

广度优先搜索（BFS）：

• 特点：一层一层地搜索图的所有顶点。
• 实现：通常使用队列来实现。
• 应用：二叉树的层序遍历就是BFS的一种应用。

这两种算法不仅适用于二叉树，也适用于图结构，无论是使用邻接表还是邻接矩阵表示的图。DFS和BFS都是用于在图或树结构中进行系统搜索的算法，它们可以解决许多问题，如查找路径、检测环、确定图的连通分量等。

深度优先搜索理论基础

DFS 与 BFS 区别

• 深度优先搜索（DFS）是沿着一个方向深入探索直到无法继续，然后回溯；
• 而广度优先搜索（BFS）是逐层遍历节点，先访问所有相邻节点再逐层深入。

dfs 搜索过程

想象你正在探索一个迷宫，迷宫的每个房间通过门与其他房间相连。你的目标是找到从入口到出口的一条路径。

1. 开始：你站在迷宫的入口房间（我们称之为“起点”）。
2. 选择方向：你选择一扇门进入下一个房间（我们称之为“房间A”）。
3. 深入探索：在房间A中，你再次选择一扇门进入下一个房间，继续这个过程，直到你到达一个没有门的房间（即“死胡同”）。
4. 回溯：既然没有更多的门可以探索，你返回到上一个房间，选择另一扇未尝试的门，继续探索。
5. 重复：你重复这个过程，每次深入探索新的路径，直到你找到出口或者探索完所有可能的路径。
6. 找到出口：最终，你找到了通往出口的路径。

在这个例子中，深度优先搜索的过程就像你在迷宫中的行为：你总是尽可能深入地探索一条路径，直到无法再前进，然后返回并尝试其他路径，直到找到目标。这个过程可以用递归算法或使用栈的数据结构来实现。

代码框架

回顾一下回溯法的代码框架：

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

回溯算法，其实就是dfs的过程，这里给出dfs的代码框架：

void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}

可以发现dfs的代码框架和回溯算法的代码框架是差不多的。

深搜三部曲

其实深搜也是一样的，深搜三部曲如下：

1. 确认递归函数，参数

void dfs(参数)

通常我们递归的时候，我们递归搜索需要了解哪些参数，其实也可以在写递归函数的时候，发现需要什么参数，再去补充就可以。

一般情况，深搜需要 二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局变量，避免让我们的函数参数过多。

例如这样：

vector<vector<int>> result; // 保存符合条件的所有路径
vector<int> path; // 起点到终点的路径
void dfs (图，目前搜索的节点)  

2. 确认终止条件

终止条件很重要，很多同学写dfs的时候，之所以容易死循环，栈溢出等等这些问题，都是因为终止条件没有想清楚。

if (终止条件) {存放结果;return;
}

终止添加不仅是结束本层递归，同时也是我们收获结果的时候。

另外，其实很多dfs写法，没有写终止条件，其实终止条件写在了， 下面dfs递归的逻辑里了，也就是不符合条件，直接不会向下递归。这里如果大家不理解的话，没关系，后面会有具体题目来讲解。

3. 处理目前搜索节点出发的路径

一般这里就是一个for循环的操作，去遍历 目前搜索节点 所能到的所有节点。

for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果
}

在深度优先搜索（DFS）中，"回溯"是一个关键的概念，它允许算法在探索完一条路径后返回到之前的节点，尝试其他可能的路径。这个过程是DFS能够探索所有可能路径的核心机制。

为什么需要回溯？

在DFS中，你从一个起始节点开始，沿着路径深入探索，直到达到一个没有未访问邻接节点的节点（即“死胡同”）。在这一点上，算法需要返回到上一个节点，尝试其他未探索的路径。这就是回溯的需要：它允许算法“撤销”之前的移动，以便探索其他可能的路径。

疑惑的地方，都是 dfs代码框架中for循环里分明已经处理节点了，那么 dfs函数下面 为什么还要撤销的呢。

如图七所示， 路径2 已经走到了 目的地节点6，那么 路径2 是如何撤销，然后改为 路径3呢？

其实这就是 回溯的过程，撤销路径2，走换下一个方向。

题目

题目一：98. 所有可达路径

98. 所有可达路径

解题思路：

邻接矩阵

邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。

本题我们会有n 个节点，因为节点标号是从1开始的，为了节点标号和下标对齐，我们申请 n + 1 * n + 1 这么大的二维数组。

vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));

输入m个边，构造方式如下：

while (m--) {cin >> s >> t;// 使用邻接矩阵 ，1 表示 节点s 指向 节点tgraph[s][t] = 1;
}

邻接表

邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。

邻接表的构造相对邻接矩阵难理解一些。

这里表达的图是：

• 节点1 指向 节点3 和 节点5
• 节点2 指向 节点4、节点3、节点5
• 节点3 指向 节点4
• 节点4指向节点1

我们需要构造一个数组，数组里的元素是一个链表。

C++写法：

// 节点编号从1到n，所以申请 n+1 这么大的数组
vector<list<int>> graph(n + 1); // 邻接表，list为C++里的链表

输入m个边，构造方式如下：

while (m--) {cin >> s >> t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);
}

本题我们使用邻接表 或者 邻接矩阵都可以，因为后台数据并没有对图的大小以及稠密度做很大的区分。

注意邻接表 和 邻接矩阵的写法都要掌握！

深度优先搜索

深搜三部曲来分析题目：

1. 确认递归函数，参数

首先我们dfs函数一定要存一个图，用来遍历的，需要存一个目前我们遍历的节点，定义为x。

还需要存一个n，表示终点，我们遍历的时候，用来判断当 x==n 时候 标明找到了终点。

（其实在递归函数的参数 不容易一开始就确定了，一般是在写函数体的时候发现缺什么，参加就补什么）

至于 单一路径 和 路径集合 可以放在全局变量，那么代码是这样的：

vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 0节点到终点的路径
// x：目前遍历的节点
// graph：存当前的图
// n：终点
void dfs (const vector<vector<int>>& graph, int x, int n) {

2. 确认终止条件

什么时候我们就找到一条路径了？

当目前遍历的节点 为 最后一个节点 n 的时候 就找到了一条 从出发点到终止点的路径。

// 当前遍历的节点x 到达节点n 
if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;
}

3. 处理目前搜索节点出发的路径

接下来是走 当前遍历节点x的下一个节点。

首先是要找到 x节点指向了哪些节点呢？ 遍历方式是这样的：

for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点if (graph[x][i] == 1) { // 找到 x指向的节点，就是节点i}
}

接下来就是将 选中的x所指向的节点，加入到 单一路径来。

path.push_back(i); // 遍历到的节点加入到路径中来

进入下一层递归

dfs(graph, i, n); // 进入下一层递归

最后就是回溯的过程，撤销本次添加节点的操作。

该过程整体代码：

for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点if (graph[x][i] == 1) { // 找到 x链接的节点path.push_back(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.pop_back(); // 回溯，撤销本节点}
}

打印结果

ACM格式大家在输出结果的时候，要关注看看格式问题，特别是字符串，有的题目说的是每个元素后面都有空格，有的题目说的是 每个元素间有空格，最后一个元素没有空格。

1. 严格遵循题目要求：输出格式应与题目描述完全一致，包括空格、换行和标点符号。
2. 元素间的空格：确保每个输出元素之间正确地添加或省略空格。
3. 最后一个元素后的处理：
   • 有些题目要求在最后一个元素后不加空格。
   • 有些题目可能要求在最后一个元素后加空格。

例如示例输出是：

1 3 5` 而不是 `1 3 5

即 5 的后面没有空格！

以上代码中，结果都存在了 result数组里（二维数组，每一行是一个结果），最后将其打印出来。（重点看注释）

// 输出结果
if (result.size() == 0) cout << -1 << endl;
for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) { // 这里指打印到倒数第二个cout << pa[i] << " ";}cout << pa[pa.size() - 1]  << endl; // 这里再打印倒数第一个，控制最后一个元素后面没有空格
}

本题代码

邻接矩阵写法

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径void dfs (const vector<vector<int>>& graph, int x, int n) {// 当前遍历的节点x 到达节点n if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;}for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点if (graph[x][i] == 1) { // 找到 x链接的节点path.push_back(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.pop_back(); // 回溯，撤销本节点}}
}int main() {int n, m, s, t;cin >> n >> m;// 节点编号从1到n，所以申请 n+1 这么大的数组vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));while (m--) {cin >> s >> t;// 使用邻接矩阵 表示无线图，1 表示 s 与 t 是相连的graph[s][t] = 1;}path.push_back(1); // 无论什么路径已经是从0节点出发dfs(graph, 1, n); // 开始遍历// 输出结果if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1]  << endl;}
}

邻接表写法

#include <iostream>
#include <vector>
#include <list>
using namespace std;vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径void dfs (const vector<list<int>>& graph, int x, int n) {if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;}for (int i : graph[x]) { // 找到 x指向的节点path.push_back(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.pop_back(); // 回溯，撤销本节点}
}int main() {int n, m, s, t;cin >> n >> m;// 节点编号从1到n，所以申请 n+1 这么大的数组vector<list<int>> graph(n + 1); // 邻接表while (m--) {cin >> s >> t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);}path.push_back(1); // 无论什么路径已经是从0节点出发dfs(graph, 1, n); // 开始遍历// 输出结果if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1]  << endl;}
}

广度优先搜索理论基础

广搜（bfs）是一圈一圈的搜索过程，和深搜（dfs）是一条路跑到黑然后再回溯。

广搜的使用场景

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

当然，也有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。

广搜的过程

广度优先搜索（BFS）是一种图遍历算法，它从一个起始节点开始，逐层（或一圈一圈）地向外扩展，直到找到目标节点或遍历完所有可达节点。BFS常用于在无权图中找到从起点到终点的最短路径。

BFS的特点：

1. 逐层搜索：BFS从起点开始，先访问所有直接相邻的节点（第一层），然后访问这些节点的相邻节点（第二层），依此类推。
2. 使用队列：BFS通常使用队列数据结构来管理待访问的节点，确保按照广度优先的顺序进行访问。
3. 最短路径：由于BFS按层次遍历，一旦找到终点，它所经过的路径必然是最短的。

简单例子： 假设你在一个5x5的网格地图上，从左上角（0,0）位置开始，目标是到达右下角（4,4）位置。地图中的每个格子可以向上、下、左、右移动，但不能斜着移动。

1. 起点：从（0,0）开始，你可以向四个方向（上、下、左、右）移动。
2. 第一层：你移动到（0,1）、（1,0）、（0,-1）、（-1,0）。
3. 第二层：然后，你从这四个新位置继续向四个方向移动，覆盖更多的格子。
4. 重复：这个过程不断重复，直到你到达（4,4）或者所有可达的格子都被访问过。

在这个过程中，BFS会记录每个节点的前一个节点，这样一旦到达终点，就可以通过这些记录回溯到起点，形成一条完整的路径。

总结： BFS是一种有效的图遍历算法，特别适用于在无权图中寻找最短路径。它通过逐层搜索和使用队列来管理待访问的节点，确保每个节点都被访问且只被访问一次。一旦找到目标节点，就可以通过回溯确定最短路径。

代码框架

广度优先搜索（BFS）的“一圈一圈”搜索过程是通过使用合适的数据结构来实现的，主要目的是保证搜索的顺序性和系统性。以下是关键点的总结：

1. 容器选择：可以使用队列、栈或数组来实现BFS。每种数据结构都会影响搜索的顺序。
2. 队列：
   • 特点：先进先出（FIFO）。
   • 搜索顺序：保持一致的方向（如总是顺时针或逆时针）。
   • 原因：队列保证了元素的加入和弹出顺序一致，使得搜索过程可以系统地逐层进行。
3. 栈：
   • 特点：先进后出（LIFO）。
   • 搜索顺序：可能在每一层改变方向（如第一层顺时针，第二层逆时针）。
   • 原因：栈的后进先出特性使得搜索可以在每一层改变方向。
4. 数组：
   • 特点：静态存储，需要额外的逻辑来控制搜索顺序。
   • 搜索顺序：需要手动管理，可能不如队列和栈直观。
5. 广度优先搜索的顺序：
   • 重要性：对于找到最短路径，搜索的顺序并不重要，因为BFS保证一旦找到目标，它就是最短路径。
   • 习惯：尽管使用栈也可以实现BFS，但使用队列更为常见，因为它直观地支持逐层搜索。尽管理论上可以使用队列、栈或数组来实现BFS，但队列是最常用的选择，因为它自然地支持逐层、系统性地搜索。

下面给出广搜代码模板，该模板针对的就是，上面的四方格的地图： （详细注释）

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素int curx = cur.first;int cury = cur.second; // 当前节点坐标for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问}}}}