牛客25606题解：DFS计算树结构最优解
https://dajuwangluo.cn/zb_users/upload/2025/07/202507111752236568166248.jpg一、问题理解牛客25606题要求我们计算树结构中的最优解，这个问题可以转化为寻找树的最长路径（直径）问题。通过DFS遍历树结构，我们可以高效地解决这类典型的图论问题。二、算法核心思想[*]树结构表示：使用邻接表存储树
[*]DFS遍历：深度优先搜索计算最大深度
[*]公式推导：利用数学公式2*(N-1)-max_depth得出结果
三、完整代码实现（带注释）
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph;
vector<bool> visited;
int max_depth = 0;
void dfs(int node, int depth) {
visited = true;
max_depth = max(max_depth, depth);
for (int neighbor : graph) {
if (!visited) {
dfs(neighbor, depth + 1);
}
}
}
int main() {
int N;
cin >> N;
graph.resize(N + 1);
visited.resize(N + 1, false);
for (int i = 0; i < N - 1; ++i) {
int X, Y;
cin >> X >> Y;
graph.push_back(Y);
graph.push_back(X);
}
dfs(1, 0);
cout << 2 * (N - 1) - max_depth << endl;
return 0;
}
关键知识点
[*]邻接表：高效存储树结构的数据结构
[*]DFS算法：深度优先搜索的基本原理
[*]递归实现：DFS的递归实现方式
[*]树的性质：树是无向无环连通图
来源：牛客25606题解：DFS计算树结构最优解
页:
[1]