【笔记】数据结构与算法之最小生成树（Kruskal算法）
import java.io.BufferedReader;import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static class Edge{
int a,b,w;
public Edge(int a,int b, int w){
this.a = a;
this.b = b;
this.w = w;
}
}
static int n,m;
//总的边
static int cnt = 0;
static Edge[] edges;
static int [] p;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] s = bf.readLine().split(" ");
n = Integer.parseInt(s);
m = Integer.parseInt(s);
edges = new Edge;
p = new int;
for(int i =1 ;i<=n;i++){
p = i;
}
for(int i = 0; i < m; i++){
String[] res = bf.readLine().split(" ");
int x = Integer.parseInt(res);
int y = Integer.parseInt(res);
int w = Integer.parseInt(res);
edges = new Edge(x,y,w);
}
//权重从小到大排序
Arrays.sort(edges,(a,b) -> a.w - b.w);
//最小生成树权重之和
int res =0;
for (int i = 0; i < m; i++) {
Edge e = edges;
int x = find(e.a);
int y = find(e.b);
if (x!=y){
res+=e.w;
p =y;
cnt++;
}
}
if(cnt<n-1){
System.out.println("failed");
}else {
System.out.println(res);
}
}
public static int find(int x){
if (p !=x){
p = find(p);
}
return p;
}
}
在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中
页:
[1]