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

Question

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

假设所有边都距离为1.

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

Answer 1

解决方案与 BFS 类似，但有一点变化：

1. 从 S = F 开始，标记 F 个节点。

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

3. 取 |S| 的并集 在 S' 中设置上面的集合并标记这些节点。如果 S' 为空，则返回“None”。

4. 返回步骤 2。

假设所有集合操作都需要常数时间，那么算法的复杂度与BFS相同，为O(|V| + |E|)。

现在来推理集合运算的复杂性。我的理由是，集合操作不会增加复杂性，因为步骤 2 和步骤 3 中的并集和交集操作可以组合起来花费时间 O(|S|)，并且因为每一步 S 都与之前迭代中的 S 不同，集合运算的总体复杂度为 O(|V|)。