java - 连接图中最近点的最佳方法

Question

我有点(城市)数组，我正在寻找如何找到 10 个最近的点并将它们连接起来创建图表的最佳方法。每个点必须正好有 10 个连接。

点类别:

public class City 
{
    int key;
    public int population;
    Point position;

    City(int key, int population, Point position)
    {
        this.key = key;
        this.population = population;
        this.position = position;
    }

    void setPopulation(int newPopulation)
    {
        this.population = newPopulation;
    }
}

现在我将所有点都放在一个数组中:

City[] cities = new City[3000];

所有点都有坐标(所有坐标都是五的倍数，因为我必须确定每个点都有距离超过 5(公里)的最近点。

所有城市都是随机生成的，因此第一个城市可以位于左上角，数组中的第二个城市可以位于右下角。

这就是我绘制所有点时的样子。

现在我需要建议，如何找到最近的点以及如何将它们连接起来创建图表。

有什么建议吗？感谢大家的回复。

Answer 1

一个相对快速的解决方案是在每个点上使用经过调整的广度优先搜索，并与其遇到的前 10 个点建立连接。