给定图形 g =（ v，e ），无方向和失重，我们想找到直径的值> Graph的D G 。显示如何找到一个值x，以使x＆lt; = d＆lt; = 2*x在O（| V | | e |）的运行时间中。
现在，要找到图形的实际直径，您只需要两次运行BFS。从任意节点和最扩散的节点中运行BFS。但是在这个问题中，我需要找到直径的近似值。我的猜测是一次运行BFS并选择最大距离作为直径。可能会发生两种边缘情况。
当选择的节点位于图 g 的周围时，第一个发生。扩展节点将位于周长的另一侧，因此 x 等于 d 。
当所选节点位于 g 和 x 的中心时，第二种情况将发生等于 d 的一半（<在这种情况下，em> x 将是g的无线电。
这是我对这个问题的回答。但是我得到了15/25。是否有一个我没有处理的边缘案例或从一开始就错了？
预先感谢您。
60％似乎对这种以前的算法TA有些苛刻 - 您给出了正确的算法，并确定了两个不平等的极端情况。尽管如此，我同意阿米特的观点，您需要给予正式证明。如果您的毕业生特别严格，您可能需要对您的算法是线性时间的说法说一两个字。
这是正式证明的开始。令d（v，w）为顶点v和w之间的路径的最小长度。直径定义为d = max_ {v，w} d（v，w）。您的算法选择一个任意的顶点s并输出x = max_ {w} d（s，w）。
您需要做一点代数以显示两个事实：x＆lt; = d and d＆lt; = 2 x。c）> = d（a，c），可容纳所有顶点A，B，C，以及对称性d（a，b）= d（b，a）。