java实现 聚类算法之MST算法
在介绍最小生成树算法（MST）之前，简单说一下平均链接算法（average-link）的实现过程，平均链接聚类算法和单链接类似，多了计算聚类之间距离矩阵的步骤
实现步骤如下：
1，将元素各成一组，把这些组放入容器H
2，循环元素距离数组，根据两层下标得到将要比较的两个元素A,B
3，在H中分别查找含有A，B的组AH，BH。假如AH不等于BH（也就是A，B不同组）， AH和BH的距离累加A，B的距离。
4，得到组间距离数组后，循环比较组间距离与阀值，小于阀值，则此两组合并成一组，合并之前把H中的两个作为比较的原始组删除。
MST算法比较有意思点，不仅用于聚类，还可以解决最短铺路成本这类问题。
我们假设一个场景：现在想在多个城市之间铺网络，怎样才是最短距离？每个城市当作一个数据点，每个点间的距离称为一个边，最短距离实际上就是求得每个点都能连成边，但是又不会回路的情况。
实现过程如下：
1，首先建立城市类和边类，如下
01
/**
02
* 城市
03
*
04
* <a href="http://my.oschina.net/arthor" class="referer" target="_blank">@author</a> duyf
05
*
06
*/
07
class City {
08
09
private String name;
10
// 经度
11
private double x;
12
13
// 纬度
14
private double y;
15
16
public double getX() {
17
return x;
18
}
19
20
public void setX(double x) {
21
this.x = x;
22
}
23
24
public double getY() {
25
return y;
26
}
27
28
public void setY(double y) {
29
this.y = y;
30
}
31
32
public String getName() {
33
return name;
34
}
35
36
public void setName(String name) {
37
this.name = name;
38
}
39
40
public boolean equals(Object obj) {
41
if (obj == null) {
42
return false;
43
}
44
if (this == obj) {
45
return true;
46
}
47
City other = (City) obj;
48
if (this.getX() == other.getX() && this.getY() == other.getY()) {
49
return true;
50
}
51
return false;
52
}
53
}
54
55
/**
56
* 边距 包含两端数据点(城市)的索引
57
* <a href="http://my.oschina.net/arthor" class="referer" target="_blank">@author</a> duyf
58
*
59
*/
60
class Edge {
61
62
private int i;
63
private int j;
64
private double w;
65
66
Edge(int i, int j, double w) {
67
this.i = i;
68
this.j = j;
69
this.w = w;
70
}
71
72
public int getI() {
73
return i;
74
}
75
76
public int getJ() {
77
return j;
78
}
79
80
public double getW() {
81
return w;
82
}
83
84
}
2，MST核心类，Edge类表示一个边的两点和距离，
找最短距离的边的过程是：不断的纳入最短边，并且再根据这些已知的最短边的两端寻找最短边（md 这句话我也感觉绕口 但应该是最通俗的了）
01
public class MST {
02
03
private List<City> data;
04
05
private double[][] ds;
06
07
public MST(List<City> data){
08
this.data=data;
09
}
10
11
public List<Edge> compute(){
12
// 距离矩阵
13
ds = new double[data.size()][data.size()];
14
15
for (int i = 0; i < data.size(); i++) {
16
City city1 = data.get(i);
17
for (int j = i + 1; j < data.size(); j++) {
18
City city2 = data.get(j);
19
ds[i][j] = getDistance(city1, city2);
20
// 矩阵 对称性
21
ds[j][i] = ds[i][j];
22
}
23
ds[i][i] = 0.0;
24
}
25
26
boolean[] isMst=new boolean[data.size()];
27
isMst[0]=true;
28
Edge edge=null;
29
List<Edge> edges=new ArrayList<Edge>();
30
while((edge=findMinEdge(isMst))!=null){
31
edges.add(edge);
32
&nbs
补充：软件开发 , Java ,
