問題描述

二維平面上有許多點p(x , y)，按照彼此之間的歐式距離進行分為若干個集合。若點p1(x1, y1)與點p(x2, y2)之間距離小于d,則認為二者是鄰居。

算法思路

給數據集的點進行編號，順序遍歷這些點，找出當前點的鄰居，記住已經遍歷過的點，直到遍歷完數據集

代碼實現

import java.util.ArrayList;
import java.util.List;import static java.awt.geom.Point2D.distance;public class Leetcode {// 聚類算法，列表a是節點列表，d是每個集合內任意兩點的最短距離public static List<List> spe(List<Node> a, int d) {List<List> r = new ArrayList<>();boolean[] visited = new boolean[a.size()];if (a.size() == 0) return r;for (int i = 0; i < a.size(); i++) {if (visited[a.get(i).index] == false)dfs(a, i, r, visited, new ArrayList<>(), d);}return r;}static void dfs(List<Node> a, int i, List<List> r, boolean[] visited, List<Node> cur, int d) {Node current = a.get(i);cur.add(current);visited[current.index] = true;boolean hasNeighbor = false;for (int j = 0; j < a.size(); j++) {if (j != i && visited[a.get(j).index] == false && distance(current.x, current.y, a.get(j).x, a.get(j).y) <= d) {hasNeighbor = true;dfs(a, j, r, visited, cur, d);}}if (hasNeighbor == false) {r.add(new ArrayList(cur));}}static class Node {double x;   // x坐標double y;    // y坐標int index;   // 在數據集的編號public Node(double[] x, int index) {this.x = x[0];this.y = x[1];this.index = index;}}public static void main(String[] args) {double[] point1 = {1.0, 2.0};double[] point2 = {2.0, 3.0};Node node1 = new Node(point1, 0);Node node2 = new Node(point2, 1);double[] point3 = {11.0, 22.0};double[] point4 = {14.0, 22.0};Node node3 = new Node(point3, 2);Node node4 = new Node(point4, 3);List<Node> t = new ArrayList<>();t.add(node1);t.add(node2);t.add(node3);t.add(node4);List<List> r = spe(t, 10);System.out.println(r);}}