二维坐标中，两点可以连成线，多个点连成的线就构成了图。
当然图也可以就一个节点，甚至没有节点（空图）
整体上一般分为 有向图 和 无向图。
有向图是指 图中边是有方向的：
无向图是指 图中边没有方向：
加权有向图，就是图中边是有权值的，
加权无向图也是同理。
无向图中有几条边连接该节点，该节点就有几度。
在有向图中，每个节点有出度和入度。
在图中表示节点的连通情况，我们称之为连通性。
连通图
在无向图中，任何两个节点都是可以到达的，我们称之为连通图。
如果有节点不能到达其他节点，则为非连通图，
强连通图
在有向图中，任何两个节点是可以相互到达的，我们称之为 强连通图。
强连通图是在有向图中任何两个节点是可以相互到达
连通分量
在无向图中的极大连通子图称之为该图的一个连通分量。
必须是极大联通子图才能是连通分量
强连通分量
在有向图中极大强连通子图称之为该图的强连通分量
我们如何用代码来表示一个图呢？
一般使用邻接表、邻接矩阵 或者用类来表示。
主要是 朴素存储、邻接表和邻接矩阵。
邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
例如： 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矩阵，造成时间浪费
邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。
有多少边 邻接表才会申请多少个对应的链表节点。
从图中可以直观看出 使用 数组 + 链表 来表达 边的连接情况 。
邻接表的优点：
对于稀疏图的存储，只需要存储边，空间利用率高
遍历节点连接情况相对容易
缺点：
检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
实现相对复杂，不易理解
深度优先搜索（dfs）
广度优先搜索（bfs）
二叉树的递归遍历，是dfs 在二叉树上的遍历方式。
二叉树的层序遍历，是bfs 在二叉树上的遍历方式。
dfs 和 bfs 一种搜索算法，可以在不同的数据结构上进行搜索，在二叉树章节里是在二叉树这样的数据结构上搜索。
而在图论章节，则是在图（邻接表或邻接矩阵）上进行搜索。
dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
上面说道dfs是可一个方向搜，不到黄河不回头。 那么我们来举一个例子。
如图一，是一个无向图，我们要搜索从节点1到节点6的所有路径。
上图演示中，其实我并没有把 所有的 从节点1 到节点6的dfs（深度优先搜索）的过程都画出来，那样太冗余了，但 已经把dfs 关键的地方都涉及到了，关键就两点：
搜索方向，是认准一个方向搜，直到碰壁之后再换方向
换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。
正是因为dfs搜索可一个方向，并需要回溯，所以用递归的方式来实现是最方便的。
有递归的地方就有回溯，那么回溯在哪里呢？
就递归函数的下面，例如如下代码：
void dfs(参数) {
处理节点
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
可以看到回溯操作就在递归函数的下面，递归和回溯是相辅相成的。
回归回溯法的代码框架
void backtracking(参数) {
if (终止条件) {
存放结果;`在这里插入代码片`
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
回溯算法，就是dfs的过程，如下：
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
}
1、确认递归函数
一般情况，深搜需要 二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局变量，避免让我们的函数参数过多。
例如：
vector<vector<int>> result; // 保存符合条件的所有路径
vector<int> path; // 起点到终点的路径
void dfs (图，目前搜索的节点)
2、确认终止条件
终止条件很重要，很多同学写dfs的时候，之所以容易死循环，栈溢出等等这些问题，都是因为终止条件没有想清楚。
if (终止条件) {
存放结果;
return;
}
终止添加不仅是结束本层递归，同时也是我们收获结果的时候。
另外，其实很多dfs写法，没有写终止条件，其实终止条件写在了， 下面dfs递归的逻辑里了，也就是不符合条件，直接不会向下递归。这里如果大家不理解的话，没关系，后面会有具体题目来讲解。
3、处理目前搜索节点发出的路径
一般这里就是一个for循环的操作，去遍历 目前搜索节点 所能到的所有节点。
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
不少录友疑惑的地方，都是 dfs代码框架中for循环里分明已经处理节点了，那么 dfs函数下面 为什么还要撤销的呢。
如图七所示， 路径2 已经走到了 目的地节点6，那么 路径2 是如何撤销，然后改为 路径3呢？ 其实这就是 回溯的过程，撤销路径2，走换下一个方向。
邻接矩阵解法
#include<iostream>
#include <vector>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void dfs(const vector<vector<int>>& graph, int x, int 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);//遍历到连接的节点装入path；
dfs(graph, i, n);//进入下一层递归；
path.pop_back();//回溯，撤掉本节点；
}
}
}
int main()
{
int n,m,s,t;
cin >> n >> m;
vector<vector<int>> graph(n+1, vector<int>(n+1,0));
while(m--)
{
cin >> s >> t;
graph[s][t] = 1;
}
//从节点0进行出发；
path.push_back(1);
dfs(graph, 1, n);
//s输出结果
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;
}
}