C++树直径算法详解（从零开始掌握树的最长路径求解）

求树直径的经典方法

求树的直径有多种方法，但最常用且高效的是两次BFS/DFS法。其核心思想如下：

1. 任选一个起点（比如节点0），进行一次BFS或DFS，找到离它最远的节点A；
2. 再以节点A为起点，进行第二次BFS或DFS，找到离A最远的节点B；
3. 那么A到B的路径长度就是树的直径。

这个方法的正确性基于树的性质：从任意点出发的最远点一定是直径的一个端点。

C++实现树直径算法

下面我们用C++实现上述算法。假设输入是一棵无向树，以邻接表形式存储。

#include <iostream>#include <vector>#include <queue>#include <algorithm>using namespace std;// BFS函数：返回 {最远节点, 最大距离}pair<int, int> bfs(int start, const vector<vector<int>>& graph) {    int n = graph.size();    vector<int> dist(n, -1);    queue<int> q;        dist[start] = 0;    q.push(start);        while (!q.empty()) {        int u = q.front();        q.pop();                for (int v : graph[u]) {            if (dist[v] == -1) {                dist[v] = dist[u] + 1;                q.push(v);            }        }    }        // 找到距离最大的节点    int maxDist = 0, farthestNode = start;    for (int i = 0; i < n; ++i) {        if (dist[i] > maxDist) {            maxDist = dist[i];            farthestNode = i;        }    }        return {farthestNode, maxDist};}// 求树的直径int treeDiameter(const vector<vector<int>>& graph) {    // 第一次BFS：从节点0出发找最远点A    pair<int, int> first = bfs(0, graph);    int nodeA = first.first;        // 第二次BFS：从A出发找最远点B，此时的距离就是直径    pair<int, int> second = bfs(nodeA, graph);    return second.second; // 返回直径长度（边数）}int main() {    // 示例：构建一棵5个节点的树    // 边: 0-1, 1-2, 2-3, 3-4    int n = 5;    vector<vector<int>> graph(n);        // 添加无向边    auto addEdge = [&](int u, int v) {        graph[u].push_back(v);        graph[v].push_back(u);    };        addEdge(0, 1);    addEdge(1, 2);    addEdge(2, 3);    addEdge(3, 4);        cout << "树的直径为: " << treeDiameter(graph) << endl;    // 输出: 树的直径为: 4        return 0;}

算法复杂度分析

该算法执行了两次BFS，每次BFS的时间复杂度为O(V + E)，其中V是节点数，E是边数。由于树满足E = V - 1，因此总时间复杂度为O(V)。空间复杂度也是O(V)，用于存储图和距离数组。

扩展：二叉树的直径

如果你处理的是二叉树（每个节点最多有两个子节点），也可以用递归方式求直径。此时直径可能不经过根节点，需要记录每个节点的左右子树最大深度之和。

这种变体常出现在面试题中，属于二叉树直径求解的经典问题。

总结

通过本文，我们学习了如何使用C++实现树的最长路径（即树的直径）的高效算法。无论是通用树还是二叉树，掌握这些技巧都能让你在算法竞赛或面试中游刃有余。记住，核心思想是“两次搜索找最远点”，这是解决C++图论算法中许多问题的关键思路。

希望这篇教程能帮助编程小白轻松入门树直径问题！动手写一遍代码，你会理解得更深刻。