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怎么实现最小生成树这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！