java kruskal怎么实现最小生成树

这篇文章主要讲解了“java kruskal怎么实现最小生成树”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“java kruskal怎么实现最小生成树”吧！

话不多说了，看代码：

import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; /** P1861 Network  D题 - 最小生成树： kruskal 4 6 1 2 1 1 3 1 1 4 2 2 3 1 3 4 1 2 4 1 1 4 1 2 1 3 2 3 3 4  * @author 姚林涛  *  */ public class Main {	static int N,M; 	static int[] SET; //并查集数组	static ArrayList<Line> lines; //图存储，边集存储	static boolean[] visited; //访问标记	static int maxLine ;//最大距离	public static void main(String[] args) {	Scanner sc = new Scanner(System.in);	//接收参数	N = sc.nextInt();	M = sc.nextInt();	maxLine = 0;	SET = new int[N+1];	visited = new boolean[M];	lines = new ArrayList<Line>();	for (int i = 0; i < M; i++) {	int s = sc.nextInt();	int e = sc.nextInt();	int v = sc.nextInt();	new Line(s,e,v);	lines.add(new Line(s,e,v));	}	//排序	Collections.sort(lines);	//查并集	init();	for (int i = 0; i < lines.size(); i++) {	if(!isConntect(lines.get(i).s,lines.get(i).e)) {	union(lines.get(i).s,lines.get(i).e);	maxLine = lines.get(i).v; // 最后一次肯定是最大长度	visited[i] = true;	}	}	//计算个数	int count = N-1;	System.out.println(maxLine);	System.out.println(count);	for (int i = 0; i < lines.size(); i++) {	if(visited[i]) {	System.out.println(lines.get(i).s+" "+lines.get(i).e);	}	}	sc.close();	}	/**	 *   将  b的根节点，指向a的根节点	 * @param a	 * @param b	 */	private static void union(int a, int b) {	int tempA = SET[a];	int tempB = SET[b];	if(tempA!=tempB) {	SET[tempB] = tempA;	}	}	/**	 * a,b 是否连接	 * @param a	 * @param b	 * @return	 */	private static boolean isConntect(int a, int b) {	return find(a)==find(b);	}	/**	 *   返回 a 的根节点	 * @param b	 * @return	 */	private static int find(int a) {	if(SET[a] == a) {	return a;	}else {	SET[a] = find(SET[a]);	return SET[a]; 	}	}	/**	 *  并查集 初始化	 */	private static void init() {	for (int i = 1; i < SET.length; i++) {	SET[i] = i;	}	}	static class Line implements Comparable<Line>{	public int s;	public int e;	public int v;	public Line(int s, int e, int v) {	this.s = s;	this.e = e;	this.v = v;	}	@Override	public int compareTo(Line o) {	if(this.v != o.v) {	return this.v - o.v; 	}else {	return this.s - o.s;	}	}	} }

感谢各位的阅读，以上就是“java kruskal怎么实现最小生成树”的内容了，经过本文的学习后，相信大家对java kruskal怎么实现最小生成树这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！