IT评测·应用市场-qidao123.com技术社区

标题: 图论--DFS搜索图/树 [打印本页]
作者: 络腮胡菲菲    时间: 2025-4-16 10:56
标题: 图论--DFS搜索图/树
目录
一、图的存储结构
二、题目练习
846. 树的重心 - AcWing题
           dfs，之前学习的回溯算法好多都是用dfs实现搜索的（把题目抽象成树形结构来搜索），实在 回溯算法就是 深搜，只不过针对某一搜索场景 我们给他一个更细分的定义，叫做回溯算法。
  本节专门解说dfs在图上的应用，需要做的就是① 明白图的存储结构（毗邻矩阵、毗邻表），② 背模版 ③  刷题 
  一、图的存储结构

看这篇博文就OK
图的存储方式总结：如何高效表示顶点与边的关系？-CSDN博客
最复杂的写法也就是 vector<vector<pair<int, int>>> g  ，虽然看起来复杂，但是比力好理解，这里我是跟着卡哥学习的写法，之前yxc大佬的数组写法呜呜呜我真的只能一时理解不能恒久记忆，也写过相关博客条记 ACWing【846】树的重心、图中点的层次 、毗邻表存储图/树、dfs/bfs搜索图/树_图中点的层次acwing-CSDN博客
其时写完应该是明白的，但是现在看真的一头雾水。。。。。
二、题目练习

        之前细致学过的部分，这里温习一下就好啦，看这篇博客 ，里面有四道经典例题（那很经典了）深度优先搜索DFS-从入门到醒目【卡玛】_
   所有可达路径属于---模版题，搜索1--n的所有路径并输出
  
  岛屿问题用来练习网格连通块识别问题
  
  博客中有四道经典例题~回顾之后下面再练习几道新题
   明白用什么存储图
  图是有向边吗照旧无向边？ 会有重边吗？需要利用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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4