dfs和bfs的区别
- dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
- bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
注意
dfs的过程图看随想录上面写的，注意几点：
- 搜索方向，是认准一个方向搜，直到碰壁之后再换方向（碰壁是指程序运行到最后一层了，不能再往下走了。）
- 换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程（回溯是一次只回溯一步，比如第5层回溯到第4层，不可以直接从第5层回溯到第3层）。
回溯算法这一章节全部都都是dfs，就是用递归来实现的，递归的代码框架如下：
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
}
下面用一个树的遍历来写一下dfs代码：
这里的dfs没有终止条件，是因为每一个节点我都需要收集。
/*
先通过两种形式构建树
1、边的形式
2、father数组
再使用dfs遍历这棵树，打印所有节点。
*/
#include <bits/stdc++.h>
using namespace std;
// 先定义一个邻接表数组，长度为100000，每一个元素都是vector<int>
vector<int> adjlist[100005];
// 存储前序遍历的结果
vector<int> result;
// 向下递归需要的参数是根节点及其父亲节点
void dfs(int node, int parent)
{
result.push_back(node);
// 从当前节点node往它的子节点开始递归
for (auto &child : adjlist[node])
{
// 因为这里是双向图，所以父节点一定也是在子节点的邻接表里面，要避免这种返祖现象！！！
if (child != parent)
{
// 此时child作为当前节点，node作为它的父节点
dfs(child, node);
}
}
}
int main()
{
int n;
cin >> n;
int type;
cin >> type;
if (type == 1)
{
// 方式一：通过边的形式输入
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
adjlist[u].push_back(v);
adjlist[v].push_back(u);
}
}
else if (type == 2)
{
// 方式二：通过father数组的形式输入
// 根节点1没有父节点，默认为0
// father[i]表示节点i+1的父节点
vector<int> father(n + 1);
// 注意这里的逻辑，输入的不是father数组，而是从father[1]开始的
for (int i = 1; i <= n; i++)
{
cin >> father[i];
// 如果不是根节点，就需要进行双向连接
if (father[i] != 0)
{
adjlist[father[i]].push_back(i);
adjlist[i].push_back(father[i]);
}
}
}
// 为了保证遍历顺序的一致性，对每个节点的子节点排序
for (int i = 1; i <= n; i++)
{
sort(adjlist[i].begin(), adjlist[i].end());
}
// 执行dfs，最原始的根节点为1，父节点为0
dfs(1, 0);
// 最终结果存在了result里面，把他按顺序打印出来
for (int i = 0; i < result.size(); i++)
{
if (i > 0) cout << " ";
cout << result[i];
}
return 0;
}