图论--DFS搜索图/树
目录一、图的存储结构
二、题目练习
846. 树的重心 - AcWing题
dfs，之前学习的回溯算法好多都是用dfs实现搜索的（把题目抽象成树形结构来搜索），实在 回溯算法就是 深搜，只不过针对某一搜索场景 我们给他一个更细分的定义，叫做回溯算法。
本节专门解说dfs在图上的应用，需要做的就是① 明白图的存储结构（毗邻矩阵、毗邻表），② 背模版 ③ 刷题
一、图的存储结构
看这篇博文就OK
图的存储方式总结：如何高效表示顶点与边的关系？-CSDN博客
最复杂的写法也就是 vector<vector<pair<int, int>>> g ，虽然看起来复杂，但是比力好理解，这里我是跟着卡哥学习的写法，之前yxc大佬的数组写法呜呜呜我真的只能一时理解不能恒久记忆，也写过相关博客条记 ACWing【846】树的重心、图中点的层次 、毗邻表存储图/树、dfs/bfs搜索图/树_图中点的层次acwing-CSDN博客
其时写完应该是明白的，但是现在看真的一头雾水。。。。。
二、题目练习
之前细致学过的部分，这里温习一下就好啦，看这篇博客 ，里面有四道经典例题（那很经典了）深度优先搜索DFS-从入门到醒目【卡玛】_
所有可达路径属于---模版题，搜索1--n的所有路径并输出
岛屿问题用来练习网格连通块识别问题
[*]岛屿数量-----统计有多少个由“1”组成的互不连通区域，连通快计数问题
[*]岛屿最大面积---找最大的连通块
[*]沉默孤岛和孤岛总面积属于-------连通块/连通域标记题型
博客中有四道经典例题~回顾之后下面再练习几道新题
明白用什么存储图
图是有向边吗照旧无向边？ 会有重边吗？需要利用visited数组吗？？搜索的时间注意边界？
树的重心问题 ，如何操作树结构（实在和图没什么差别）
846. 树的重心 - AcWing题库
https://i-blog.csdnimg.cn/direct/3a9ea5839d044dcb92c8f2b2b16d55c2.png
树的重心问题，挺简单的一道题，重要是理解题意，什么是最大节点数最小？？？
这里我们利用 DFS 统计每个节点删除后各子树巨细的最大值，然后取所有节点中这个“最大值”的最小值
https://i-blog.csdnimg.cn/direct/e22eade7abbb4ede9f9ff54a2d0fbfde.png
https://i-blog.csdnimg.cn/direct/efc0460fada54d88a406a006d240cd3d.png
思路：
1. 从根节点开始DFS
2. 递归计算每个节点的所有子树规模
3. 在回溯时计算：
- 子节点方向的最大连通块
- 父节点方向的剩余连通块
4. 比较并更新全局最小值
5. 最终输出所有可能分割方案中的最优解搞清子节点和父节点！！！！很关键
子节点的巨细盘算如下图：
https://i-blog.csdnimg.cn/direct/f0bf90654e914417bcfe9fb8f7a3c904.png
父节点就是n-累加的所有子节点数啦
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10; // 最大节点数
vector<int> edges; // 邻接表存储树结构
int n; // 节点总数
int min_max = INT_MAX; // 存储最小的最大连通块大小（初始化为极大值）
/**
* 深度优先搜索计算子树信息
* @param u 当前节点
* @param parent 父节点（用于防止回溯）
* @return 以u为根的子树节点数
*/
int dfs(int u, int parent) {
int subtree_size = 1; // 当前子树节点数（至少包含自己）
int max_part = 0; // 删除u后最大的连通块大小
// 遍历所有邻接节点（包含父节点和子节点）
for (int v : edges) {
if (v == parent) continue; // 跳过父节点防止回溯
// 递归获取子树的节点数（此时u是v的父节点）
int child_size = dfs(v, u);
max_part = max(max_part, child_size); // 更新子节点方向的最大块
subtree_size += child_size; // 累加子树规模，用于计算父节点数目
}
// 子节点的最大块为max_part 父节点方向的连通块大小 = 总节点数 - 当前子树规模
max_part = max(max_part, n - subtree_size);
// 全局维护最小值（所有节点的最大连通块中的最小值）
min_max = min(min_max, max_part);
return subtree_size; // 返回当前子树的规模（给上层递归使用）
}
int main() {
// 加速输入输出（处理大规模数据时效果显著）
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
// 构建树结构（n-1条边）
for (int i = 0; i < n-1; ++i) {
int a, b;
cin >> a >> b;
edges.push_back(b); // 无向图双向连接
edges.push_back(a);
}
dfs(1, -1); // 从任意节点开始遍历（根节点设为1，父节点不存在用-1表示）
cout << min_max << endl;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]