如何在图中查找高度最大的树，求时间复杂度上限为O(n²)的算法

前提约束 #

• 输入图为正则图（所有顶点度数相同）
• 图不存在多重边与自环
• 算法时间复杂度上限要求为O(n²)，其中n为图的顶点数

核心逻辑 #

要得到高度最大的树，本质是要找到图中最长的简单路径（即图的直径），将直径的一端作为根、保留完整直径结构生成的树，高度就等于直径长度，这是当前图能得到的最大树高。

实现步骤 #

• 任选图中一个顶点u，执行BFS遍历，找到距离u最远的顶点v，该步骤时间复杂度为O(n + m)，m为图的边数
• 以顶点v为起点再次执行BFS遍历，找到距离v最远的顶点w，此时v到w的路径即为图的直径，该步骤时间复杂度为O(n + m)
• 以v为根节点执行DFS生成生成树，遍历过程优先沿直径方向访问邻接节点，保证直径路径完整保留在生成树中，最终得到的生成树就是当前图中高度最大的树，该步骤时间复杂度为O(n + m)

复杂度验证 #

对于k-正则图，边数m = k*n/2，k为正则度数是固定常数，因此单步遍历的复杂度等价于O(n)，总时间复杂度为O(n)，远低于要求的O(n²)上限。

若输入正则图为非连通图，仅需先遍历所有连通分量，对每个分量分别执行上述算法，选取高度最大的生成树即可，总时间复杂度仍不超过O(n²)。

内容的提问来源于stack exchange，提问作者Ivan Manchur