找到两个顶点子集之间的miniums距离

Question

给定无向图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 |)中运行

Answer 1

国际海事组织你可以做的如下:

1. 扫描集合V1并记下从V1节点开始的所有边缘,并在不在V1中的节点处结束.
2. 现在将V1中的所有节点组合成一个节点.步骤1中记录的边缘应是从该节点出来的边缘.
3. 为V2做同样的事情.
4. 现在它减少了节点V1和V2之间的最短路径问题.这可以通过在节点V1上进行简单的BFS或在O(E)中进行V2来解决,其中E是图中边缘的数量.