小编son*_*mbo的帖子

给定无向图G =(V,E),V1,V2是V的子集 d(V1,V2)=min d(v1,v2),
所以我需要弄清楚如何找到d(V1,V2) O(|V|+|E|)

如果 然后 d(V1,V2)=0

否则,我从V1中随机选择v1'并运行BFS(V1,v1'),从v1'保存最远的顶点v1''我将对来自V2的一些随机顶点v2'执行相同的操作.return d(V1,V2)= min {d(v1',v2'),d(v1',v2''),d(v1''v2'),d(v1'',v2'')}

那会有用吗？由于BFS的运行时为O(| V | + | E |),因此建议的算法将在O(| V | + | E |)中运行