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

当然图也可以就一个节点，甚至没有节点（空图）

整体上一般分为 有向图 和 无向图。

有向图是指 图中边是有方向的：

​​

无向图是指 图中边没有方向：

​​

加权有向图，就是图中边是有权值的，例如：

​​

加权无向图也是同理。

无向图中有几条边连接该节点，该节点就有几度。

例如，该无向图中，节点4的度为5，节点6的度为3。

​​

在有向图中，每个节点有出度和入度。

出度：从该节点出发的边的个数。

入度：指向该节点边的个数。

例如，该有向图中，节点3的入度为2，出度为1，节点1的入度为0，出度为2。

​​

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

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

​​

如果有节点不能到达其他节点，则为非连通图，如图：

​​

节点1 不能到达节点4。

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

这里有录友可能想，这和无向图中的连通图有什么区别，不是一样的吗？

我们来看这个有向图：

​​

这个图是强连通图吗？

初步一看，好像这节点都连着呢，但这不是强连通图，节点1 可以到节点5，但节点5 不能到 节点1 。

强连通图是在有向图中任何两个节点是可以相互到达

下面这个有向图才是强连通图：

​​

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

只看概念大家可能不理解，我来画个图：

​​

该无向图中 节点1、节点2、节点5 构成的子图就是 该无向图中的一个连通分量，该子图所有节点都是相互可达到的。

同理，节点3、节点4、节点6 构成的子图 也是该无向图中的一个连通分量。

那么无向图中 节点3 、节点4 构成的子图 是该无向图的联通分量吗？

不是！

因为必须是极大联通子图才能是连通分量，所以 必须是节点3、节点4、节点6 构成的子图才是连通分量。

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

如图：

​​

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

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

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

我们如何用代码来表示一个图呢？

一般使用邻接表、邻接矩阵 或者用类来表示。

主要是 朴素存储、邻接表和邻接矩阵。

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

例如： grid[2][5] = 6，表示 节点 2 连接 节点5 为有向图，节点2 指向 节点5，边的权值为6。

如果想表示无向图，即：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与 节点5 相互连通，权值为6。

如图：

​​

在一个 n （节点数）为8 的图中，就需要申请 8 * 8 这么大的空间。

图中有一条双向边，即：grid[2][5] = 6，grid[5][2] = 6

这种表达方式（邻接矩阵） 在 边少，节点多的情况下，会导致申请过大的二维数组，造成空间浪费。

而且在寻找节点连接情况的时候，需要遍历整个矩阵，即 n * n 的时间复杂度，同样造成时间浪费。

邻接矩阵的优点：

• 表达方式简单，易于理解
• 检查任意两个顶点间是否存在边的操作非常快
• 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

缺点：

• 遇到稀疏图，会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费

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

邻接表的构造如图：

​​

这里表达的图是：

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

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

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

邻接表的优点：

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

缺点：

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

图的遍历方式基本是两大类：

• 深度优先搜索（dfs）
• 广度优先搜索（bfs）

在讲解二叉树章节的时候，其实就已经讲过这两种遍历方式。

二叉树的递归遍历，是dfs 在二叉树上的遍历方式。

二叉树的层序遍历，是bfs 在二叉树上的遍历方式。

以上知识点 大家先有个印象，上面提到的每个知识点，其实都需要大篇幅才能讲明白的。

提到深度优先搜索（dfs），就不得不说和广度优先搜索（bfs）有什么区别

先来了解dfs的过程，很多录友可能对dfs（深度优先搜索），bfs（广度优先搜索）分不清。

先给大家说一下两者大概的区别：

• dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
• bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

当然以上讲的是，大体可以这么理解，接下来 我们详细讲解dfs，（bfs在用单独一篇文章详细讲解）

上面说道dfs是可一个方向搜，不到黄河不回头。 那么我们来举一个例子。

如图一，是一个无向图，我们要搜索从节点1到节点6的所有路径。

​​

那么dfs搜索的第一条路径是这样的： （假设第一次延默认方向，就找到了节点6），图二

​​

此时我们找到了节点6，（遇到黄河了，是不是应该回头了），那么应该再去搜索其他方向了。 如图三：

​​

路径2撤销了，改变了方向，走路径3（红色线）， 接着也找到终点6。 那么撤销路径2，改为路径3，在dfs中其实就是回溯的过程（这一点很重要，很多录友不理解dfs代码中回溯是用来干什么的）

又找到了一条从节点1到节点6的路径，又到黄河了，此时再回头，下图图四中，路径4撤销（回溯的过程），改为路径5。

​​

又找到了一条从节点1到节点6的路径，又到黄河了，此时再回头，下图图五，路径6撤销（回溯的过程），改为路径7，路径8 和 路径7，路径9， 结果发现死路一条，都走到了自己走过的节点。

​​

那么节点2所连接路径和节点3所链接的路径 都走过了，撤销路径只能向上回退，去选择撤销当初节点4的选择，也就是撤销路径5，改为路径10 。 如图图六：

​​

上图演示中，其实我并没有把 所有的 从节点1 到节点6的dfs（深度优先搜索）的过程都画出来，那样太冗余了，但 已经把dfs 关键的地方都涉及到了，关键就两点：

• 搜索方向，是认准一个方向搜，直到碰壁之后再换方向
• 换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。

正是因为dfs搜索可一个方向，并需要回溯，所以用递归的方式来实现是最方便的。

在 二叉树递归讲解中，给出了递归三部曲。

我们讲解了，dfs 和 bfs的大体区别（bfs详细过程下篇来讲），dfs的搜索过程以及代码框架。

最后还有 深搜三部曲来解读这份代码框架。

以上如果大家都能理解了，其实搜索的代码就很好写，具体题目套用具体场景就可以了。

后面我也会给大家安排具体练习的题目，依旧是代码随想录的风格，循序渐进由浅入深！

本题和力扣 797.所有可能的路径 ​**(opens new window)** 是一样的，录友了解深度优先搜索之后，这道题目就是模板题，是送分题。

力扣是核心代码模式，把图的存储方式给大家定义好了，只需要写出深搜的核心代码就可以。

如果笔试的时候出一道原题 （笔试都是ACM模式，部分面试也是ACM模式），不少熟练刷力扣的录友都难住了，因为不知道图应该怎么存，也不知道自己存的图如何去遍历。

所以这也是为什么我要让大家练习 ACM模式

这道题目是深度优先搜索，比较好的入门题。

如果对深度优先搜索还不够了解，可以先看这里：深度优先搜索的理论基础(opens new window)

我依然总结了深搜三部曲，如果按照代码随想录刷题的录友，应该刷过 二叉树的递归三部曲，回溯三部曲。

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

本题我们会有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;
}

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

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

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

有的题目呢，压根没说，那只能提交去试一试了。

很多录友在提交题目的时候发现结果一样，为什么提交就是不对呢。

例如示例输出是：

​1 3 5​ 而不是 1 3 5​

即 5 的后面没有空格！

这是我们在输出的时候需要注意的点。

有录友可能会想，ACM格式就是麻烦，有空格没有空格有什么影响，结果对了不就行了？

ACM模式相对于核心代码模式（力扣） 更考验大家对代码的掌控能力。 例如工程代码里，输出输出都是要自己控制的。这也是为什么大公司笔试，都是ACM模式。

以上代码中，结果都存在了 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;
}
}

本题是一道简单的深搜题目，也可以说是模板题，和 力扣797. 所有可能的路径 ​**(opens new window)** 思路是一样一样的。

很多录友做力扣的时候，轻松就把代码写出来了， 但做面试笔试的时候，遇到这样的题就写不出来了。

在力扣上刷题不用考虑图的存储方式，也不用考虑输出的格式。

而这些都是 ACM 模式题目的知识点（图的存储方式）和细节（输出的格式）

所以我才会特别制作ACM题目，同样也重点去讲解图的存储和遍历方式，来帮大家去练习。

对于这种有向图路径问题，最合适使用深搜，当然本题也可以使用广搜，但广搜相对来说就麻烦了一些，需要记录一下路径。

而深搜和广搜都适合解决颜色类的问题，例如岛屿系列，其实都是 遍历+标记，所以使用哪种遍历都是可以的。

至于广搜理论基础，我们在下一篇在好好讲解，敬请期待！