图的直径与半径求解算法

题目描述
给定一个无向连通图G=(V,E)，其中每条边的权重均为1（即无权图）。图的直径（diameter）定义为图中任意两个顶点之间最短距离的最大值，而半径（radius）则定义为所有顶点到其他顶点的最大距离（即偏心距）的最小值。要求设计高效算法计算图的直径和半径。

基础概念澄清

1. 顶点v的偏心距（eccentricity）e(v) = max{d(v,u) | u∈V}，其中d(v,u)表示v到u的最短距离
2. 直径 = max{e(v) | v∈V}
3. 半径 = min{e(v) | v∈V}
4. 中心点（center）是使偏心距等于半径的顶点

步骤1：暴力解法思路分析
最直接的方法是计算所有顶点对之间的最短距离：

• 对每个顶点执行BFS（因为边权为1，BFS即可得最短距离）
• 记录每个顶点到其他顶点的最大距离（即偏心距）
• 最终取所有偏心距的最大值作为直径，最小值作为半径
  时间复杂度：O(V*(V+E))，对于稀疏图近似O(V²)

步骤2：优化策略——使用任意顶点BFS
观察性质：从任意顶点s执行BFS后，距离s最远的顶点t一定是直径的端点候选。
具体步骤：

1. 随机选择顶点a，执行BFS找到最远顶点b（b的偏心距e(a)=d(a,b)）
2. 从顶点b执行BFS找到最远顶点c（此时e(b)=d(b,c)）
3. 此时直径diameter = d(b,c)
   原理说明：在树结构中该性质显然成立，但在一般图中需证明。实际上该性质对所有无权连通图成立：设真实直径为D，端点x和y。由于b是离a最远的点，有d(a,b)≥d(a,y)；同理d(b,c)≥d(b,x)。通过三角不等式可证明d(b,c)=D。

步骤3：半径的精确计算
注意：上述方法只能得到直径，无法直接得到半径。需要额外步骤：

1. 在获得直径端点b和c后，记录从b和c执行BFS得到的所有顶点距离
2. 对每个顶点v，其偏心距e(v) ≥ max{d(b,v), d(c,v)}
3. 实际上存在更强结论：e(v) = max{d(b,v), d(c,v)}
4. 因此只需计算每个顶点到b和c的距离，取最大值作为偏心距，再求最小值即得半径

步骤4：算法实现细节

def graph_diameter_radius(graph):
    # 第一次BFS：随机起点（实际取0号顶点）
    dist1 = BFS(graph, 0)
    b = max(range(len(dist1)), key=lambda i: dist1[i])
    
    # 第二次BFS：从b出发
    dist_b = BFS(graph, b)
    c = max(range(len(dist_b)), key=lambda i: dist_b[i])
    diameter = dist_b[c]
    
    # 第三次BFS：从c出发
    dist_c = BFS(graph, c)
    
    # 计算每个顶点的偏心距
    eccentricities = [max(dist_b[i], dist_c[i]) for i in range(len(graph))]
    radius = min(eccentricities)
    
    return diameter, radius

步骤5：正确性证明
关键点在于为什么e(v)=max{d(b,v), d(c,v)}：

• 由三角不等式，对任意顶点u，d(v,u) ≤ d(v,b) + d(b,u) ≤ d(v,b) + D
• 同理d(v,u) ≤ d(v,c) + d(c,u) ≤ d(v,c) + D
• 但更重要的是，对于任意顶点v，必然存在d(v,b)或d(v,c)至少为D/2
• 结合直径端点性质，可证明max{d(b,v), d(c,v)}就是v的偏心距

步骤6：复杂度分析

• 执行3次BFS，每次时间复杂度O(V+E)
• 计算偏心距和极值O(V)
• 总时间复杂度O(V+E)，优于暴力算法的O(V²)
• 空间复杂度O(V)存储距离数组

总结
该算法通过三次BFS巧妙利用图直径的性质，将看似需要全源最短路径的问题转化为线性复杂度。其中直径端点寻找的两次BFS法（称为"两遍BFS法"）是图论中的经典技巧，适用于所有无权连通图。