java - Java 中的 k 最近邻图实现

Question

我正在实现 Flame 聚类算法，以此来学习更多关于图和图遍历的知识，第一步是构建 K-最近邻图，我想知道最快的方法是什么是运行一个节点列表并连接每个节点只是说，它是最近的五个邻居。我的想法是，我将从一个节点开始，遍历其他节点的列表并将最接近的节点保留在一个数组中，确保丢弃超过前 n 个的所有节点。现在，我可以通过对列表进行排序并保留前 n 个条目来做到这一点，但我宁愿在内存中保留更少的东西，所以我想知道是否有办法只拥有最终数组并将该数组更新为我遍历，或者是否有更有效的方法来生成 k 最近邻图。

另外，请注意，这不是 K-Nearest Neighbour Implementation in Java 的副本. KNNG 与 KNN 不同。

Answer 1

放置前n个节点，在一个列表中排序。然后遍历其余节点，如果它适合当前列表(即是前n个节点)，则将其放在列表中的相应位置并丢弃最后一个前n个节点。如果它不适合前 n 个列表，则丢弃它。

for each neighborNode
 for(int i = 0; i < topNList.size(); i++){
       if((dist = distanceMetric(neighborNode,currentNode)) > topNList.get(i).distance){
             topNList.remove(topNList.size()-1)
             neighborNode.setDistance(dist);
             topNList.add(i, neighborNode);
       }