如何从给定的一组节点等距离地查找图中的所有节点？

Question

如果你有一个简单的无向图G(V,E)和F这是V的子集。你怎么能找到一些节点v，使得从F到v的每个节点的距离是相同的，距离是最小的？如果没有v，请返回None。我被告知这可以在O(|V|+|E|)的复杂性。

假设所有边缘的距离为1.

任何人都可以解释如何做到这一点吗？伪代码也有帮助。

Answer 1

的解决方案是类似于BFS，但有一点变化：

1. 开始使用S = F为F节点标记。

2. 查找| S |在S中的每个元素设置距离为1（所有这些集应该包含未标记的节点）。如果这些集合的交集非空，则找到候选者。

3. 以| S |在S'中设置以上并标记这些节点。如果S'为空，则返回'无'。

4. 返回到步骤2。

假设所有该组操作采取恒定时间，则算法的复杂度是相同BFS其是O（| V | + | E |）。

现在推理设置操作的复杂性。我的推理是集合运算不会增加复杂性，因为步骤2和3中的并集和交集操作可以合并以花费时间O（| S |），并且由于在每一步中S与以前迭代中的S不同，设置操作的整体复杂度将是O（| V |）。

Answer 2

下面是一个伪代码算法，试图添加注释来解释它是如何工作的。

declare explored // a table of all the vertices that can keep track of one number (distance, initialized to -1) and a list of vertex references (origins, initialized to null) 
to_explore = S // fifo queue of vertices to explore 

while (to_explore not empty) { 
    pop vertex v from to_explore 
    current_distance = explored[v].distance 
    current_origins = explored[v].origins 
    for (vertex n, neighbor of v) { 
     if (explored[n].origins contains v) 
      continue // we just hit a loop and we're only interested in shortest distances 
     if (explored[n].distance == -1) { // first time we come here 
      explored[n].distance = current_distance+1 
      explored[n].origins = current_origins 
      push n to to_explore 
      continue 
     } 
     if (explored[n].distance != current_distance+1) { 
      continue // we are merging path from another node of S but different distance, cannot lead to any solution 
     } 
     // only case left is explored[n].distance == current_distance+1 
     // so we've already come here from other place(s) in S with the same distance 
     add/merge (without duplicates) origins to explored[n].origins 
     if (explored[n].origins = S) // maybe compare the size is enough? 
      return n // we found a solution 
     // if not , we just continue our exploration, no need to add to the queue since we've already been through here before 
    } 
} 

的想法是，与FIFO队列中，我们将探讨一切，在距离1从集合S，如果我们不能找到任何解决方案在那里，一切都在距离2 ...等等。所以我们我会先找到最短的距离。

我对复杂性并不完全确定，但我认为在最糟糕的情况下，我们只探索每个顶点和每个边缘一次，以便给出O(|E| + |V|)。但在某些情况下，我们多次访问同一个顶点。尽管这并没有增加探索的路径，但我不确定是否应该有一个因素| S |某处（但如果那只是认为像一个常数，那么没关系......）

希望我没有错过任何东西。很显然，我没有测试任何这.... :)

编辑（回复评论）

请问像这样的图你的代码的工作？ （a，b），（a，c），（a，d） ，（b，e），（c，e），（d，e）和我的F = {b，c，d} 。说，你用a开始你的 bfs。我怀疑，最后，源数组将只有{a} ，因此代码将返回None。 - 大师Devanla

在这种情况下，会出现以下情况：

to_explore is initialized to {b,c,d} 
//while (to_explore not empty) 
pop one from to_explore (b). to_explore becomes {c,d} 
current_distance=0 
current_origins={b} 
//for (neighbors of b) { 
handling 'a' as neighbor of b first 
explored[a].distance=1 
explored[a].origins={b} 
to_explore becomes {c,d,a} 
//for (neighbors of b) 
handling 'e' as next neighbor of b 
explored[e].distance=1 
explored[e].origins={b} 
to_explore becomes {c,d,a,e} 
//while (to_explore not empty) 
pop one from to_explore (c). to_explore becomes {d,a,e} 
current_distance=0 
current_origins={c} 
//for (neighbors of c) 
handling 'a' as neighbor of c first 
explored[a].distance is already 1 
explored[a].origins={b,c} 
to_explore already contains a 
//for (neighbors of c) { 
handling 'e' as next neighbor of b 
explored[e].distance is already 1 
explored[e].origins={b,} 
to_explore already contains e 
//while (to_explore not empty) 
pop one from to_explore (d) 
current_distance=0 
current_origins={d} 
//for (neighbors of d) 
handling 'a' as neighbor of d first 
explored[a].distance is already 1 
explored[a].origins={b,c,d} 
that matches F, found a as a solution.