# 1、什么是图？
一幅图是由节点和边构成的，逻辑结构如下：
图一般有两种存储结构分为：
- 邻接表
- 邻接矩阵
// 邻接表 // graph[x] 存储 x 的所有邻居节点 vector<vector<int>> graph // 邻接矩阵 // matrix[x][y] 记录 x 是否有一条指向 y 的边 vector<vector<int>> matrix复制成功
1
2
3
4
5
6
7
2
3
4
5
6
7
# 2、dfs算法模板
void dfs(参数) { 处理节点; if (终止条件) { 存放结果; 撤销处理结果；--（可选） return; // 这里也可以选择不return，那就没有必要撤销了 } for (选择：本节点所连接的其他节点) { dfs(图，选择的节点); // 递归 } 回溯，撤销处理结果 }复制成功
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 3、dfs和回溯算法的区别
这里先给出回溯算法的模板
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }复制成功
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
相同点：
- dfs也是回溯算法的一种，都是递归思想的具体体现
不同点：
- 回溯算法的「做选择」和「撤销选择」在 for 循环里面，而dfs算法在for循环外面
- 回溯算法关注的不是节点，而是树枝。
- dfs算法关注节点。是因为一个图可以有独立的节点，他们之间没有边进行连接。
