algorithm - 如何找到图中与给定节点集等距的所有节点？

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' 为空，则返回 'None'。

4. 返回第 2 步。

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

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