algorithm - 计算距 m 个给定节点的距离小于 k 的所有节点的最佳方法

Question

尺寸图n给出了大小为 m 的子集给出了它的节点。查找位于 distance <=k 的所有节点来自子集的所有节点。

例如。 A->B->C->D->E 是图形，subset = {A,C} , k = 2.

现在，E 与 C 的距离 <=2，但与 A 的距离不超过 2，因此不应将其计算在内。

我想从子集中的每个节点运行广度优先搜索，并取各自答案的交集。
能否进一步优化？

我浏览了很多关于 SO 的帖子，但它们都指向我不明白的 kd-trees，那么还有其他方法吗？

Answer 1

我可以想到两个非渐近(我相信)优化:

1. 如果您完成了子集节点之一的 BFS，请删除距离 > k 的所有节点
2. 从子集中距离最大的两个节点开始，得到尽可能小的剩余图

当然，如果 k 很大(接近 n)，这没有帮助，我不知道在那种情况下。但是我很肯定 k/d 树不适用于一般图:)