使用了并查集+优先队列.
具体解释等周末再描述 :shuijiao:
以下是代码:
import java.util.*;
public class Kruskal {
private int[] points;
private void initPoints(int n){
points = new int[n+1];
for(int i = 0;i<=n;i++){
points[i] = i;
}
}
private void union(int a ,int b){ int A = find(a); int B = find(b); if(A != B){ points[A] = B; } } private boolean connect(int a,int b){ int A = find(a); int B = find(b); return A==B; } private int find(int a){ if(points[a] == a){ return points[a]; } else{ return points[a] = find(points[a]); } } private void doKruskal(int pointCnt,int[][] edges){ PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() { @Override public int compare(int[] ints, int[] t1) { return ints[2]-t1[2]; } }); List<int[]> newEdges = new ArrayList<>(); Collections.addAll(pq, edges); initPoints(pointCnt); int[] minWeightEdge; while(!pq.isEmpty()){ minWeightEdge = pq.poll(); if(!connect(minWeightEdge[0],minWeightEdge[1])){ union(minWeightEdge[0],minWeightEdge[1]); newEdges.add(new int[]{minWeightEdge[0],minWeightEdge[1]}); } } for(int[] newEdge:newEdges){ System.out.println(Arrays.toString(newEdge)); } } public static void main(String[] args) { Kruskal k = new Kruskal(); int[][] edges = new int[][]{ {1,2,12}, {1,4,16}, {1,3,14}, {2,4,7}, {2,5,10}, {3,4,9}, {3,6,8}, {4,5,6}, {4,6,2}, {5,6,5}, {5,7,3}, {6,7,4} }; k.doKruskal(7,edges); }
}