Kruskal算法
Java 代码
import java.util.*;
public class Main{
//N代表有多少列,M代表总共有多少点,E代表总共可以连接多少条边
static final int N = 1010 , M = N * N,E = 2 * N * N;
static int n,m,k; // n行m列,一共k个点
static int[][] ids = new int[N][N]; // 左上角点为(1,1),将二维的点映射为一维
static int[] p = new int[M]; // 并查集
static Edge[] edges = new Edge[E]; // 存储边
// 路径压缩的并查集
static int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
static void get_edges() {
int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1}, du = {1, 2, 1, 2};
//这四层循环代表的是先将[i,j]和能到的点联系起来
//这里的 u = 0 代表竖边,u = 1 代表横边
for (int u = 0; u < 2; u++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int d = 0; d < 4; d++)
if (d % 2 == u) { // 保证先加入竖边
int x = i + dx[d], y = j + dy[d], w = du[d];
if (x > 0 && x <= n && y > 0 && y <= m) {
int a = ids[i][j], b = ids[x][y];
//a < b值为了防止重复
//因为上下左右这样子走 前面可以走到后面 后面的格子也可以走回前面 会重复
if (a < b) edges[k++] = new Edge(a,b,w);
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
// 将二维的点映射为一维
for (int i = 1, t = 1; i <= n; i++)
for (int j = 1; j <= m; j++, t++){
ids[i][j] = t;
}
//总共有 n * m 个点
for (int i = 1; i <= n * m; i++) p[i] = i;
int x1, y1, x2, y2;
while (sc.hasNext()) {
x1 = sc.nextInt();
y1 = sc.nextInt();
x2 = sc.nextInt();
y2 = sc.nextInt();
//ids存储的值是二维下标对应的一维下标值
int a = ids[x1][y1], b = ids[x2][y2];
//将已连线的边添加进并查集
p[find(a)] = find(b);
}
get_edges(); // 建立所有的边
int res = 0;
for (int i = 0; i < k; i++) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a);
b = find(b);
//a 和 b 不在一个连通块内,则连起来
if (a != b) {
p[a] = b;
res += w;
}
}
System.out.println(res);
}
}
class Edge {
int a, b, w;
public Edge(int a,int b,int w){
this.a = a;
this.b = b;
this.w = w;
}
};