当前位置：首页 > 牛客 > 牛客25606题解：图论算法和深度优先搜索求解树直径 C++代码示例

牛客25606题解：图论算法和深度优先搜索求解树直径 C++代码示例

2个月前 (08-28)

一、题目解读

牛客25606题要求处理一棵树结构，通过给定的节点连接关系，计算并输出树直径（即最长路径）的长度。题目难点在于如何高效遍历树并找到最长路径，需结合图论算法与深度优先搜索（DFS）思想。

二、解题思路

解题关键在于利用DFS遍历树，同时记录遍历深度。通过单次DFS从任意节点出发，找到最远距离节点（即树的直径一端），再以该节点为起点进行第二次DFS，获取的最远距离即为树直径。巧妙利用“树的直径必经过最深节点”的性质，避免复杂计算。

三、解题步骤

1. 输入处理：读取节点数N及N-1条边，构建无向图（邻接表存储）。

2. 初始化：visited数组标记未访问节点，max_depth记录当前最大深度。

3. 第一次DFS：从节点1开始，递归遍历并更新max_depth，找到最深节点u。

4. 第二次DFS：以u为起点，再次遍历获取最深节点v，u-v路径即为直径。

5. 计算直径长度：直径长度=2×(N-1)-深度（因直径包含所有边，总边数2×(N-1)，减去单路径深度差）。

6. 输出结果：最终答案输出。

四、代码与注释

#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[node] = true; // 标记访问
    max_depth = max(max_depth, depth); // 更新深度
    
    for (int neighbor : graph[node]) { // 遍历邻居节点
        if (!visited[neighbor]) { // 未访问则递归
            dfs(neighbor, depth + 1);
        }
    }
}

int main() {
    int N;
    cin >> N; // 输入节点数
    graph.resize(N + 1); // 初始化图
    visited.resize(N + 1, false); // 初始化visited数组
    
    for (int i = 0; i < N - 1; ++i) {
        int X, Y;
        cin >> X >> Y; // 输入边
        graph[X].push_back(Y); // 双向添加边
        graph[Y].push_back(X);
    }
    
    dfs(1, 0); // 第一次DFS，找最深节点
    cout << 2 * (N - 1) - max_depth << endl; // 计算并输出直径
    return 0;
}