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怎么實現最小生成樹這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！