最小生成树

我们定义无向连通图的 最小生成树 （Minimum Spanning Tree，MST）为边权和最小的生成树。

以下实现皆是基于LeetCode 5513题：连接所有点的最小费用的实现

1
2
3
4
5
6
7
连接所有点的最小费用
 
给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

Kruskal 算法

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Kruskal {

	static class Edge implements Comparable<Edge>{
		int x,y,len;

		public Edge(int x, int y, int len) {
			this.x = x;
			this.y = y;
			this.len = len;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.len,o.len);
		}
	}

	int[] f ; //并查集find数组

	public int find(int x) {    //find函数，判断是否同一个root节点
		return f[x] == x ? x : find(f[x]);
	}

	public int minCostConnectPoints(int[][] points) {
		int h = points.length;
		f=new int[h+1];
		for (int i = 0; i < f.length; i++) {//初始化find数组，让初始每个节点都自成一个集合，互相不联通
			f[i]=i;
		}
		ArrayList<Edge> edges = new ArrayList<>();
		//求边长
		for (int i = 0; i < h; i++) {
			for (int j = i + 1; j < h; j++) {
				int len = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
				if (len != 0) {
					edges.add(new Edge(i, j, len));
				}
			}
		}
		int ans =0;
		Collections.sort(edges);
		for(Edge e:edges){
			int x=e.x;
			int y =e.y;
			int len = e.len;
			if(find(x)==find(y)) { //如果两个节点是同一个集合中，说明之前已经有其他路径连过了
				continue;
			}
			ans+=len;
			f[find(x)] = find(y);//把两集合合并
		}
		return ans;
	}
}

Prim算法

Prim 算法是另一种常见并且好写的最小生成树算法。该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Prim {

	public int minCostConnectPoints(int[][] ps) {
		int len = ps.length;
		int res = 0;
		boolean[] vis = new boolean[len];
		int[] min_dist = new int[len];
		Arrays.fill(min_dist,Integer.MAX_VALUE);
		min_dist[0] = 0;
		for (int i = 0; i <len ; i++) {         // 每次选取最小距离的点访问
			int u = -1;
			int gmin = Integer.MAX_VALUE;
			for (int j = 0; j <len ; j++) {
				if(!vis[j] && min_dist[j] < gmin){
					gmin = min_dist[j];
					u  = j;
				}
			}
			res += gmin;
			vis[u] = true;
			for (int j = 0; j <len ; j++) {     // 更新当前加入点 与 其他没加入点的最小距离
				if(!vis[j]){
					int new_dist = Math.abs(ps[j][0] - ps[u][0]) + Math.abs(ps[j][1] - ps[u][1]);
					min_dist[j] = Math.min(min_dist[j],new_dist);
				}
			}
		}
		return res;
	}
}