java kruskal怎么實(shí)現(xiàn)最小生成樹

這篇文章主要講解了“java kruskal怎么實(shí)現(xiàn)最小生成樹”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“java kruskal怎么實(shí)現(xiàn)最小生成樹”吧！

話不多說(shuō)了，看代碼：

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; //并查集數(shù)組
	static ArrayList<Line> lines; //圖存儲(chǔ)，邊集存儲(chǔ)
	static boolean[] visited; //訪問標(biāo)記
	static int maxLine ;//最大距離
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//接收參數(shù)
		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; // 最后一次肯定是最大長(zhǎng)度
				visited[i] = true;
			}
		}
		//計(jì)算個(gè)數(shù)
		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的根節(jié)點(diǎn)，指向a的根節(jié)點(diǎn)
	 * @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 的根節(jié)點(diǎn)
	 * @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怎么實(shí)現(xiàn)最小生成樹”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)java kruskal怎么實(shí)現(xiàn)最小生成樹這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！