小编Ste*_*phM的帖子

我必须给出一个算法如下：

给定一个无向连通图 G，给出一个算法，找到两个节点 x,y，使得它们的距离至少是图直径的一半。证明任何主张。

我假设我必须从任意节点运行 BFS 并找到最远的节点来找到直径。然后找到两个探索的节点，其距离大于直径的一半。但我怀疑这是最佳的并要求解决方案。有没有其他方法可以在运行 BFS 时找到直径，同时找到这两个所需的节点？这样复杂度仍然是多项式。任何指导或提示将不胜感激！