C++如何求解树的直径-C++-PHP中文网

能，两次BFS/DFS一定能找到树的直径，前提是图是无环连通无向图；第一次从任一节点出发找到最远点（直径一端），第二次从该点出发找到最远距离即为直径长度。

c++如何求解树的直径

两次BFS/DFS一定能找到树的直径吗

能，但前提是图必须是无环连通无向图（即一棵真正的树）。对任意树，从任一节点出发做一次BFS或DFS，到达的最远节点一定是直径的一个端点；再从该端点出发做第二次BFS/DFS，最远距离就是直径长度。这个性质成立的关键在于树的唯一路径性——任意两点间只有一条简单路径。

常见错误现象：dist[0]初始化为0但没清零全局数组，导致第二次遍历时残留上次结果；或者误把有向图、带环图当作树来跑，得到错误结果。

务必确认输入是连通且无环的——可通过边数是否等于n-1 + DFS遍历节点数是否为n双重验证
使用邻接表而非邻接矩阵，避免O(n²)空间和超时（尤其n > 1e5时）
BFS比DFS更稳妥：避免递归栈溢出，且天然支持记录路径（若还需输出直径上的点）

用BFS实现时怎么记录最远节点和距离

核心是维护一个dist数组和一个prev数组（可选），每次BFS结束后扫描dist找最大值及其下标。不需要额外标记“是否为直径端点”，只需两次调用：

int bfs(int start, vector<int>& dist, const vector<vector>>& g) {
    fill(dist.begin(), dist.end(), -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    // 返回最远节点编号
    return max_element(dist.begin(), dist.end()) - dist.begin();
}
</int></vector></int>

注意：max_element返回迭代器，需减去begin()得下标；dist必须用-1初始化（不能用0），否则无法区分未访问节点。