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

🕗 发布于 2024-09-21 11:03 图论 leetcode 算法 数据结构 c++

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

图论理论基础Part01

图的基本概念

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

图的种类

连通性

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

连通图

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

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

强连通图

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

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

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

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

连通分量

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

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

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

强连通分量

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

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

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

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

图的构造

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

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

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

邻接矩阵

邻接矩阵是一种用二维数组表示图的方法，其中数组的元素表示顶点间的连接关系和边的权重，对于无向图，如果节点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 搜索过程

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

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

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

代码框架

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

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

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

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

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

深搜三部曲

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

确认递归函数，参数

void dfs(参数)

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

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

例如这样：

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

确认终止条件

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

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

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

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

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

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

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

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

为什么需要回溯？

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

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

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

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

题目

题目一：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 指向 节点t
    graph[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);
}

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

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

深度优先搜索

深搜三部曲来分析题目：

确认递归函数，参数

首先我们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) {

确认终止条件

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

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

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

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

接下来是走当前遍历节点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 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的特点：

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

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

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

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

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

代码框架

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

容器选择：可以使用队列、栈或数组来实现BFS。每种数据结构都会影响搜索的顺序。
队列：
- 特点：先进先出（FIFO）。
- 搜索顺序：保持一致的方向（如总是顺时针或逆时针）。
- 原因：队列保证了元素的加入和弹出顺序一致，使得搜索过程可以系统地逐层进行。
栈：
- 特点：先进后出（LIFO）。
- 搜索顺序：可能在每一层改变方向（如第一层顺时针，第二层逆时针）。
- 原因：栈的后进先出特性使得搜索可以在每一层改变方向。
数组：
- 特点：静态存储，需要额外的逻辑来控制搜索顺序。
- 搜索顺序：需要手动管理，可能不如队列和栈直观。
广度优先搜索的顺序：
- 重要性：对于找到最短路径，搜索的顺序并不重要，因为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; // 只要加入队列立刻标记，避免重复访问
            }
        }
    }

}

原文地址：https://blog.csdn.net/LuckyYH__/article/details/142372892

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：富格林：积攒经验阻挠欺诈套路
下一篇：如何解决DataGrip的 Public Key Retrieval is not allowed错误

解决 Spring Boot 中 `Ambiguous mapping. Cannot map ‘xxxController‘ method` 错误
在使用 Spring Boot 开发 Web 应用时，经常会遇到各种各样的错误。其中一种常见的错误是。本文将详细介绍这个错误的原因及解决方法，帮助开发者快速定位并解决问题。解决错误的关键在于确保每个方
阅读更多2024-11-15
数据分析案例-笔记本电脑价格数据可视化分析
本实验数据集来源于Kaggle，原始数据集共有1303条数据，13个变量，各变量含义如下：0 laptop_ID-数字-产品ID1 Company-字符串-笔记本电脑制造商2 Product-字符串-
阅读更多2024-11-15
Linux 如何查看当前系统版本的详细信息？
系统中基本都存在，所以是一种标准的获取系统信息的方式。命令以标准的方式提供详细的发行版信息。发行版的说明文件一般位于。
阅读更多2024-11-15
初级数据结构——栈
数据结构栈（Stack）是一种线性的数据结构，它只允许在序列的一端（称为栈顶）进行插入和删除操作。这种特性使得栈成为许多算法和问题解决中的有力工具。栈是一种简单而强大的数据结构，它遵循后进先出的原则，
阅读更多2024-11-15
网络安全练习之 ctfshow_web
根据前面得到的qq邮箱中的qq号查询用户，目前电脑版的QQ添加好友好像不能查看详细信息，手机版的可以看到对方所在地为陕西西安。路径是：/editor/attached/file/tmp/html/no
阅读更多2024-11-15
Python 三种方式实现自动化任务
本文介绍了用Python实现机器人过程自动化的三个包，方便读者选择、对比学习。
阅读更多2024-11-15
C++基础：Pimpl设计模式的实现
PIMPL （ Private Implementation 或 Pointer to Implementation ）是通过一个私有的成员指针，将指针所指向的类的内部实现数据进行隐藏。
阅读更多2024-11-15
【flutter】flutter2升级到3.
以这个 https://github.com/aa286211636/Flutter_QQ 为例子，升级下看看。只有登录界面能正常显示，别的页面都是报错。flutter这版本变动，基本不能直接ru
阅读更多2024-11-15
【JAVA毕业设计】基于Vue和SpringBoot的宠物咖啡馆平台
基于Vue.js和SpringBoot的宠物咖啡馆平台是一个综合性的在线服务系统，旨在为宠物爱好者提供一个便捷的宠物护理和社交场所。该平台分为管理后台和用户网页端，以满足不同用户群体的需求。管理后台主
阅读更多2024-11-15
认证鉴权框架SpringSecurity-2--重点组件和过滤器链篇
这4个接口中，每一个都是当认证或者授权过程中发生结果后触发，可以是失败的场景也可以是成功后触发。1个成功后执行，3个为失败后促发执行。
阅读更多2024-11-15

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

文章目录

图论理论基础Part01

图的基本概念

图的种类

连通性

连通图

强连通图

连通分量

强连通分量

图的构造

邻接矩阵

邻接表

图的遍历方式

深度优先搜索理论基础

DFS 与 BFS 区别

dfs 搜索过程

代码框架

深搜三部曲

为什么需要回溯？

题目

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

解题思路：

邻接矩阵

邻接表

深度优先搜索

打印结果

本题代码

邻接矩阵写法

邻接表写法

广度优先搜索理论基础

广搜的使用场景

广搜的过程

代码框架

相关文章