牛客25606题解：DFS计算树结构最优解

19339201706

一、问题理解

牛客25606题要求我们计算树结构中的最优解，这个问题可以转化为寻找树的最长路径（直径）问题。通过DFS遍历树结构，我们可以高效地解决这类典型的图论问题。

二、算法核心思想

• ‌树结构表示‌：使用邻接表存储树
• ‌DFS遍历‌：深度优先搜索计算最大深度
• ‌公式推导‌：利用数学公式2*(N-1)-max_depth得出结果
  
  

三、完整代码实现（带注释）

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. vector<vector<int>> graph;
   
6. vector<bool> visited;
   
7. int max_depth = 0;
   
8. 
   
9. void dfs(int node, int depth) {
   
10.     visited[node] = true;
    
11.     max_depth = max(max_depth, depth);
    
12.    
    
13.     for (int neighbor : graph[node]) {
    
14.         if (!visited[neighbor]) {
    
15.             dfs(neighbor, depth + 1);
    
16.         }
    
17.     }
    
18. }
    
19. 
    
20. int main() {
    
21.     int N;
    
22.     cin >> N;
    
23.     graph.resize(N + 1);
    
24.     visited.resize(N + 1, false);
    
25.    
    
26.     for (int i = 0; i < N - 1; ++i) {
    
27.         int X, Y;
    
28.         cin >> X >> Y;
    
29.         graph[X].push_back(Y);
    
30.         graph[Y].push_back(X);
    
31.     }
    
32.    
    
33.     dfs(1, 0);
    
34.     cout << 2 * (N - 1) - max_depth << endl;
    
35.     return 0;
    
36. }

复制代码

关键知识点

• ‌邻接表‌：高效存储树结构的数据结构
• ‌DFS算法‌：深度优先搜索的基本原理
• ‌递归实现‌：DFS的递归实现方式
• ‌树的性质‌：树是无向无环连通图
  
  

来源：牛客25606题解：DFS计算树结构最优解