java - 使用java的TreeMap构建最小生成树

Question

我正在从事一个项目，该项目要求我跟踪二维平面上的多个点。我需要添加允许某些点检测其他点的接近度的功能。我立即想到了最近对问题，并认为也许我应该构建一个最小生成树。

第一个问题是，这些点不断更新它们的坐标，我想知道这样做是否合理。

另一个问题是，我不能为此使用第 3 方库，所以没有 jgraph 或 jung。我想知道是否有一种方法可以仅使用我提供的库来构建最小跨度。可以使用 TreeMap 还是必须从头开始？

Answer 1

听起来您正在尝试执行最近邻 查询。那就是您尝试找到最接近另一点的一个点(或多个点)的地方。对于一个简单的解决方案，您可以只存储一个点列表并使用距离公式遍历它们以找出最接近的点。但是，如果您想更快地进行查询，则需要使用支持此类查询的空间数据结构。我建议使用 KD 树。 Java 的标准库中没有 KD 树实现，因此您需要自己实现。

TreeMap 只是 Map 接口(interface)的一个实现，它允许您通过键放置和检索值。如果您想编写一些东西来生成最小生成树，您需要自己动手。