图论--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题库

    树的重心问题，挺简单的一道题，重要是理解题意，什么是最大节点数最小？？？
  这里我们利用 DFS 统计每个节点删除后各子树巨细的最大值，然后取所有节点中这个“最大值”的最小值
  

  

  思路：

1. 1. 从根节点开始DFS
2. 2. 递归计算每个节点的所有子树规模
3. 3. 在回溯时计算：
4.    - 子节点方向的最大连通块
5.    - 父节点方向的剩余连通块
6. 4. 比较并更新全局最小值
7. 5. 最终输出所有可能分割方案中的最优解

复制代码

搞清子节点和父节点！！！！很关键
  子节点的巨细盘算如下图：
  

  父节点就是n-累加的所有子节点数啦

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N = 1e5 + 10;      // 最大节点数
5. vector<int> edges[N];        // 邻接表存储树结构
6. int n;                       // 节点总数
7. int min_max = INT_MAX;       // 存储最小的最大连通块大小（初始化为极大值）
9. /**
10. * 深度优先搜索计算子树信息
11. * @param u      当前节点
12. * @param parent 父节点（用于防止回溯）
13. * @return 以u为根的子树节点数
14. */
15. int dfs(int u, int parent) {
16.     int subtree_size = 1;    // 当前子树节点数（至少包含自己）
17.     int max_part = 0;        // 删除u后最大的连通块大小
19.     // 遍历所有邻接节点（包含父节点和子节点）
20.     for (int v : edges[u]) {
21.         if (v == parent) continue; // 跳过父节点防止回溯
23.         // 递归获取子树的节点数（此时u是v的父节点）
24.         int child_size = dfs(v, u);
25.         max_part = max(max_part, child_size); // 更新子节点方向的最大块
26.         subtree_size += child_size;    // 累加子树规模，用于计算父节点数目
27.     }
28.         
29.     // 子节点的最大块为max_part 父节点方向的连通块大小 = 总节点数 - 当前子树规模
30.     max_part = max(max_part, n - subtree_size);
31.    
32.     // 全局维护最小值（所有节点的最大连通块中的最小值）
33.     min_max = min(min_max, max_part);
35.     return subtree_size; // 返回当前子树的规模（给上层递归使用）
36. }
38. int main() {
39.     // 加速输入输出（处理大规模数据时效果显著）
40.     ios::sync_with_stdio(false);
41.     cin.tie(nullptr);
43.     cin >> n;
44.    
45.     // 构建树结构（n-1条边）
46.     for (int i = 0; i < n-1; ++i) {
47.         int a, b;
48.         cin >> a >> b;
49.         edges[a].push_back(b); // 无向图双向连接
50.         edges[b].push_back(a);
51.     }
53.     dfs(1, -1); // 从任意节点开始遍历（根节点设为1，父节点不存在用-1表示）
55.     cout << min_max << endl;
56.     return 0;
57. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。