집합 알고리즘 단일 링크 알고리즘 자바 구현

집합 알고리즘 에서 링크 를 기반 으로 하 는 알고리즘 은 크게 세 가지 가 있 습 니 다.단일 링크 알고리즘(single link),평균 링크 알고리즘(average link),최소 생 성 알고리즘(minimum spanning tree)입 니 다.현재 단일 링크 알고리즘 을 실현 하고 다른 알고리즘 은 나중에 계속 합 시다.        단일 링크 알고리즘 은 먼저 각 요소 의 거리 행렬 을 생 성하 고 거리 와 밸브 값 의 비교 에 따라 생 성 된 집합 개 수 를 제어 하 며 밸브 값 이 클 수록 생 성 된 집합 이 적 고 같은 종류 에 속 할 때 까지 생 성 됩 니 다.        아래 의 예 는 경위도 에 따라 도시 의 집합 을 실현 하 였 다. 
 
 

package test.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class SingleLinkTest {

	public static void main(String[] args) {

		List<City> citys = new ArrayList<City>();

		City city0 = new City();
		city0.setName("   ");
		city0.setX(116.28);
		city0.setY(39.54);
		citys.add(city0);

		City city1 = new City();
		city1.setName("   ");
		city1.setX(121.29);
		city1.setY(31.14);
		citys.add(city1);

		City city2 = new City();
		city2.setName("   ");
		city2.setX(117.11);
		city2.setY(39.09);
		citys.add(city2);

		City city3 = new City();
		city3.setName("   ");
		city3.setX(106.32);
		city3.setY(29.32);
		citys.add(city3);

		City city4 = new City();
		city4.setName("   ");
		city4.setX(126.41);
		city4.setY(45.45);
		citys.add(city4);

		City city5 = new City();
		city5.setName("   ");
		city5.setX(125.19);
		city5.setY(43.52);
		citys.add(city5);

		City city6 = new City();
		city6.setName("   ");
		city6.setX(118.50);
		city6.setY(32.02);
		citys.add(city6);

		City city7 = new City();
		city7.setName("   ");
		city7.setX(114.21);
		city7.setY(30.37);
		citys.add(city7);

		City city8 = new City();
		city8.setName("   ");
		city8.setX(121.31);
		city8.setY(25.03);
		citys.add(city8);

		City city9 = new City();
		city9.setName("   ");
		city9.setX(114.10);
		city9.setY(22.18);
		citys.add(city9);

		SingleLink sing = new SingleLink(citys);
		List<Set<City>> list = sing.compute();
		for (Set<City> list0 : list) {
			System.out.println("=============");
			for (City city : list0) {
				System.out.println(city.getName() + " : (" + city.getX() + ","
						+ city.getY() + ")");
			}
		}
	}

}

 
 
 
 

package test.algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *          
 */
class SingleLink {

	private List<City> data;

	//     
	private double distanceX = 8;

	public SingleLink(List<City> list) {
		data = list;
	}

	public List<Set<City>> compute() {
		List<Set<City>> list = new ArrayList<Set<City>>();

		//     
		double[][] ds = new double[data.size()][data.size()];

		for (int i = 0; i < data.size(); i++) {
			City city1 = data.get(i);
			for (int j = i + 1; j < data.size(); j++) {
				City city2 = data.get(j);
				ds[i][j] = getDistance(city1, city2);
				//       
				ds[j][i] = ds[i][j];
			}
			ds[i][i] = 0.0;
		}

		for (int i = 0; i < ds.length; i++) {
			for (int j = 0; j < ds.length; j++) {
				System.out.print((int) ds[i][j] + ",");
			}
			System.out.println();
		}

		boolean[] hasUsed = new boolean[ds.length];
		for (int i = 0; i < ds.length; i++) {
			Set<City> setDs = new HashSet<City>();
			if (hasUsed[i]) {
				continue;
			}
			for (int j = i; j < ds.length; j++) {
				if (ds[i][j] <= distanceX && hasUsed[j] == false) {
					setDs.add(data.get(j));
					hasUsed[j] = true;
				}
			}
			if (setDs.size() > 0) {
				list.add(setDs);
			}

		}
		return list;
	}

	//       
	private double getDistance(City city1, City city2) {
		double distance = Math.pow(city1.getX() - city2.getX(), 2)
				+ Math.pow(city1.getY() - city2.getY(), 2);
		return Math.sqrt(distance);

	}

}

 
 
 

package test.algorithm;

/**
 *   
 */
class City {

	private String name;
	//   
	private double x;

	//   
	private double y;

	public double getX() {
		return x;
	}

	public void setX(double x) {
		this.x = x;
	}

	public double getY() {
		return y;
	}

	public void setY(double y) {
		this.y = y;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public boolean equals(Object obj) {
		if (obj == null) {
			return false;
		}
		if (this == obj) {
			return true;
		}
		City other = (City) obj;
		if (this.getX() == other.getX() && this.getY() == other.getY()) {
			return true;
		}
		return false;
	}
}