在大量节点上寻找路径？大约 100,000 个节点
Path finding on a large list of nodes? Around 100,000 nodes
我有一个节点列表作为二维坐标（浮点数组），目标是找出有多少节点链接到源节点（给定）。
如果节点之间的距离小于或等于 10，则两个节点被定义为链接。此外，如果 A 和 B 之间的距离 <= 10，则 B 和 C 之间的距离 <= 10 并且距离在 A 和 C > 10 之间，即使这样，A 和 C 也是链接的，因为路径将是 A->B->C。因此，它在理论上是一个典型的图搜索问题。
问题出在这里。 我的列表中有大约 100,000 个节点。每个节点都是一个二维坐标点。由于列表很大，传统的遍历和路径查找算法（如 DFS 或 BFS）将占用 O(n^2) 来构建邻接列表，这并不理想，也不是我想要的。
我在互联网上进行了研究，发现在这种情况下，四叉树或 kd 树可能是最好的实现方式。我也制作了自己的四叉树 class，我只是不明白如何在其上实现像 DFS 这样的搜索算法。还是我还漏掉了什么？
四叉树通过将 2D space 分成四分之一来对点进行分组，直到每个点都有自己的象限，或者直到达到最小大小，然后将象限内的所有点集中到一个列表中.
由于您正在尝试查找源列表中每个点的最大距离内的所有点，因此您无需一直向下搜索到 one-point-per-cell。为了选择一个截止点，我会对一些不同的值进行性能测试，但是作为最小象限大小的起点，点的最大连接距离可能是一个很好的猜测。
现在您已将所有点分组到一棵树中，您需要知道如何实际找到附近的点。
由于四叉树对空间信息进行编码，要查找任何给定点一定距离内的点，您可以降低四叉树并使用该空间信息从搜索中排除整个象限。为此，您需要检查每个象限的 nearest 边界是否超出了距您正在搜索的点的最大距离。如果该象限的最近边缘超出最大距离，则该象限中的 none 个点可能在最大距离内，因此无需探索树的该部分。 （这类似于二分搜索不需要搜索排序数组或树的部分，因为它知道这些部分不可能包含要搜索的值）。
一旦下降到具有单个点或点列表的四叉树级别，您将对这些点进行常规欧氏距离检查，以查看它们是否实际上在最大距离内。 （不要忘记检查相等性，否则你会发现你正在搜索的相同点）。
因此，例如，如果您要搜索此图像 bottom-right 角中的一个点附近的点，则无需搜索其他三个 top-level 象限，因为他们三个都将超出最大距离。这将使您免于探索树的那些部分中的所有 sub-quadrants，并避免对所有这些点进行距离比较。
但是，如果您要搜索象限边缘附近的点，则需要检查相邻象限，因为最近的边界足够近，您不能排除有效点位于其中的可能性那个象限。
在您的特定情况下，您可以通过构建一次四叉树来利用它，然后遍历原始点列表并执行我上面描述的搜索以找到该点附近的所有点。然后，您将使用 found-points 构建连接图，该连接图可以被 Depth/Breadth-First-Search 有效地遍历，或者可以被赋予 edge-weights 以用于更复杂的加权搜索，如 Dijkstra 算法或A*.
我有一个节点列表作为二维坐标（浮点数组），目标是找出有多少节点链接到源节点（给定）。
如果节点之间的距离小于或等于 10，则两个节点被定义为链接。此外，如果 A 和 B 之间的距离 <= 10，则 B 和 C 之间的距离 <= 10 并且距离在 A 和 C > 10 之间，即使这样，A 和 C 也是链接的，因为路径将是 A->B->C。因此，它在理论上是一个典型的图搜索问题。
问题出在这里。 我的列表中有大约 100,000 个节点。每个节点都是一个二维坐标点。由于列表很大，传统的遍历和路径查找算法（如 DFS 或 BFS）将占用 O(n^2) 来构建邻接列表，这并不理想，也不是我想要的。
我在互联网上进行了研究，发现在这种情况下，四叉树或 kd 树可能是最好的实现方式。我也制作了自己的四叉树 class，我只是不明白如何在其上实现像 DFS 这样的搜索算法。还是我还漏掉了什么？
四叉树通过将 2D space 分成四分之一来对点进行分组，直到每个点都有自己的象限，或者直到达到最小大小，然后将象限内的所有点集中到一个列表中.
由于您正在尝试查找源列表中每个点的最大距离内的所有点，因此您无需一直向下搜索到 one-point-per-cell。为了选择一个截止点，我会对一些不同的值进行性能测试，但是作为最小象限大小的起点，点的最大连接距离可能是一个很好的猜测。
现在您已将所有点分组到一棵树中，您需要知道如何实际找到附近的点。
由于四叉树对空间信息进行编码，要查找任何给定点一定距离内的点，您可以降低四叉树并使用该空间信息从搜索中排除整个象限。为此，您需要检查每个象限的 nearest 边界是否超出了距您正在搜索的点的最大距离。如果该象限的最近边缘超出最大距离，则该象限中的 none 个点可能在最大距离内，因此无需探索树的该部分。 （这类似于二分搜索不需要搜索排序数组或树的部分，因为它知道这些部分不可能包含要搜索的值）。
一旦下降到具有单个点或点列表的四叉树级别，您将对这些点进行常规欧氏距离检查，以查看它们是否实际上在最大距离内。 （不要忘记检查相等性，否则你会发现你正在搜索的相同点）。
因此，例如，如果您要搜索此图像 bottom-right 角中的一个点附近的点，则无需搜索其他三个 top-level 象限，因为他们三个都将超出最大距离。这将使您免于探索树的那些部分中的所有 sub-quadrants，并避免对所有这些点进行距离比较。
但是，如果您要搜索象限边缘附近的点，则需要检查相邻象限，因为最近的边界足够近，您不能排除有效点位于其中的可能性那个象限。
在您的特定情况下，您可以通过构建一次四叉树来利用它，然后遍历原始点列表并执行我上面描述的搜索以找到该点附近的所有点。然后，您将使用 found-points 构建连接图，该连接图可以被 Depth/Breadth-First-Search 有效地遍历，或者可以被赋予 edge-weights 以用于更复杂的加权搜索，如 Dijkstra 算法或A*.