尺寸图n给出了大小为 m 的子集给出了它的节点。查找位于 distance <=k 的所有节点来自子集的所有节点。
例如。 A->B->C->D->E 是图形，subset = {A,C} , k = 2.
现在，E 与 C 的距离 <=2，但与 A 的距离不超过 2，因此不应将其计算在内。
我想从子集中的每个节点运行广度优先搜索，并取各自答案的交集。
能否进一步优化？
我浏览了很多关于 SO 的帖子，但它们都指向我不明白的 kd-trees，那么还有其他方法吗？
最佳答案
我可以想到两个非渐近(我相信)优化:
- 如果您完成了子集节点之一的 BFS，请删除距离 > k 的所有节点
- 从子集中距离最大的两个节点开始，得到尽可能小的剩余图
当然，如果 k 很大(接近 n)，这没有帮助，我不知道在那种情况下。但是我很肯定 k/d 树不适用于一般图:)
关于algorithm - 计算距 m 个给定节点的距离小于 k 的所有节点的最佳方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23243831/