n
的图,以及它的一个大小为m
的节点子集。找到距离该子集中所有节点距离<=k
的所有节点。
例如,给出以下图:A->B->C->D->E,
subset
= {A,C},k
=2。
现在,E和C之间的距离小于或等于2,但是与A之间的距离不满足条件,因此不应计算在内。
我考虑从子集中的每个节点开始运行广度优先搜索,并取各自答案的交。
是否可以进一步优化?
我查看了许多SO上的帖子,但它们都指向了我不理解的kd-tree,还有其他方法吗?
n
的图,以及它的一个大小为m
的节点子集。找到距离该子集中所有节点距离<=k
的所有节点。
例如,给出以下图:subset
= {A,C},k
=2。
现在,E和C之间的距离小于或等于2,但是与A之间的距离不满足条件,因此不应计算在内。
我考虑从子集中的每个节点开始运行广度优先搜索,并取各自答案的交。
是否可以进一步优化?
我查看了许多SO上的帖子,但它们都指向了我不理解的kd-tree,还有其他方法吗?
第一个是"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或交集然后集合减法的情况下使用集合减法,如果主集合具有最小化大小,则使用交集然后集合减法。
s
),并将其连接到所有给定的m
个节点。s
小于或等于k+1的所有节点,并从中减去m
。T(n)=O(V+E)
k
,在许多情况下,您的技术将考虑到不满足此条件的节点。 - Box Box Box Box