从给定的节点开始，计算距离小于k的所有节点的最佳方法是什么？

Question

给定一个大小为n的图，以及它的一个大小为m的节点子集。找到距离该子集中所有节点距离<=k的所有节点。

例如，给出以下图：
A->B->C->D->E，subset = {A,C},k=2。

现在，E和C之间的距离小于或等于2，但是与A之间的距离不满足条件，因此不应计算在内。

我考虑从子集中的每个节点开始运行广度优先搜索，并取各自答案的交。
是否可以进一步优化？

我查看了许多SO上的帖子，但它们都指向了我不理解的kd-tree，还有其他方法吗？

- Aseem Goyal

---

抱歉，我误解了您的问题，因此删除了令人困惑的评论。 - Mohit Jain

你可能想在http://cs.stackexchange.com/上提问。 - Adrian Frühwirth

@Dukeling：好的，那我等一天，如果没有得到任何答案，我就会从这里删除并发布到计算机科学版块。 - Aseem Goyal

那是一个有向图吗？ - Niklas B.

有多少边？这个图是特定类型的吗？你提供的折线图比其他类型的图形容易解决得多。 - Nuclearman

Answer 1

我可以想到两种非渐近优化方法（我认为）：

1. 如果你从子集节点中的一个节点完成了BFS，则删除所有距离它大于k的节点
2. 从距离最远的两个子集节点开始，以获得可能剩余图形最小的结果

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

- Niklas B.

---

@Nuclearman 嗯，但是这样你就无法从子图中删除节点，所以你的BFS实际上并没有被修剪，或者我漏掉了什么吗？ - Niklas B.

@Nuclearman 当然可以，但是如果你删除了这些节点，就不能从另一个节点开始进行BFS搜索，因为它可能在第一次搜索的起点周围的d半径内。 - Niklas B.

@Nuclearman，如果您已经在第一个起始点的半径内，不再连接到图形，我不明白这将如何运作。抱歉，也许我误解了您的算法。 - Niklas B.

一个公正的观点，现在我考虑得更多了，我所想的需要预处理才能正常工作，而预处理允许更多的可能性而不仅仅是那个。 - Nuclearman

@Nuclearman，我对解决这个问题的好方法非常感兴趣，如果你有什么想法，请务必写下答案 :) - Niklas B.

非常好，发布了一个可能更注重输出的答案。似乎无法解决k很大的情况，或者只是最终解决方案的大小为O（N）的情况。在有许多查询的情况下，似乎唯一的优化就是这种情况。 - Nuclearman

Answer 2

Nicklas B的优化可以应用于以下两种优化。

优化1：将BFS修改为在运行时进行交集操作，而不是之后进行。

BFS和交集似乎是正确的方法。然而，BFS执行了一些冗余的工作。具体而言，在第一个BFS之后，它扩展了不需要扩展的节点。这可以通过将交集方面合并到BFS中来解决。

解决方案似乎是保留两组节点，称它们为“ToVisit”和“Visited”，而不是标记节点是否被访问。

BFS的新规则如下：

1. 仅扩展ToVisit中的节点。然后将它们从ToVisit移动到Visited，以防止它们被扩展两次。 2. 算法将Visited集返回为其结果，而且任何留在ToVisit中的节点都会被丢弃。然后将其用作下一个节点的ToVisit集。 3. 第一个节点使用标准的BFS算法或ToVisit是所有节点的列表。无论哪种方式，结果都成为第二个节点的第二个ToVisit集。

如果ToVisit集平均较小，则效果更好，当m和k远小于N时，情况通常如此。

优化 #2：如果有足够的查询，则预先计算距离，使查询只需进行交集操作。但是，这与第一种优化不兼容。如果存在足够数量的不同子集和 k 值的查询，则最好提前找到每对节点之间的距离，成本为 O(VE)。

这样，您只需要执行交集操作，其复杂度为 O(V*M*Q)，其中 Q 是查询数量，M 是查询中子集的平均大小，V 是节点数。如果预计 O(M*Q) > O(E)，则此方法应该更少工作量。注意，两个最远的节点很有用，因为任何等于或高于 k 的值都将始终返回所有顶点的集合，在这种情况下查询成本仅为 O(V)。

然后，距离数据应以四种形式存储。

• 第一个是"kCount[A][k] = A到距离小于等于k的节点数"。这提供了一种替代Niklas B.建议的方法，即“从子集中距离最远的两个节点开始，以获得最小的剩余图形”，在O(m) > O(sqrt(V))的情况下，因为找到最小值是O(m^2)，所以避免尝试找到起始对的最佳选择可能更好，只需选择一个好的选择即可。您可以从具有给定k的最小值的子集中的两个节点开始使用此数据结构。您还可以按此指标对子集中的节点进行排序，并按该顺序执行交集。

• 第二个是"kMax[A] = A的最大k值"，可以使用哈希映射/字典完成。如果k >=此值，则可以跳过此值，除非kCount[A][kMax[A]] <（顶点数），表示无法从A到达所有节点。

• 第三个是"kFrom[A][k] = 距离A k 的节点集"，由于k有效范围为0到最大距离，因此可以在此处使用哈希映射/字典到数组/列表，而不是嵌套的哈希映射/字典。这允许高效地使用空间和时间创建从A到距离小于等于k的节点集。

• 第四个是"dist[A][B] = A到B的距离"，这可以使用嵌套的哈希映射/字典完成。这样可以相当快速地处理交集检查。

* 如果空间不是问题，那么这个结构可以存储所有距离A不超过k的节点，但这需要O(V^3)的空间和时间。然而，主要好处是它允许同时存储一个单独的节点列表，这些节点距离大于k。这使得算法可以使用较小的集合，dist > k或dist <= k。在dist <= k的情况下使用交集，在dist > k或交集然后集合减法的情况下使用集合减法，如果主集合具有最小化大小，则使用交集然后集合减法。

- Nuclearman

---

这正是我所想的，我想要另一个算法。 - Aseem Goyal

扩展答案以提供在多个查询的情况下可能的优化（Ω（V），理想情况下为Ω（V ^ 2））。 - Nuclearman

Answer 3

1. 添加一个新节点（假设为s），并将其连接到所有给定的m个节点。
2. 然后，找到距离s小于或等于k+1的所有节点，并从中减去m。T(n)=O(V+E)

- shiwang

---

这与多源BFS相同，显然在这种情况下不起作用。请仔细阅读问题。所有节点的最大距离必须为k，在许多情况下，您的技术将考虑到不满足此条件的节点。 - Box Box Box Box