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

搞清子节点和父节点！！！！很关键

子节点的大小计算如下图：

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

#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;      // 最大节点数
vector<int> edges[N];        // 邻接表存储树结构
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[u]) {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[a].push_back(b); // 无向图双向连接edges[b].push_back(a);}dfs(1, -1); // 从任意节点开始遍历（根节点设为1，父节点不存在用-1表示）cout << min_max << endl;return 0;
}