使用Kruskal算法求解Java最小生成树问题

在电子电路中，我们通常需要较少的接线来将引脚连接在一起。我们可以使用连接的无向图G =(V,E)来建模此布线问题，其中V是引脚组，E是引脚对之间可能的互连组，对于每个边，我们都有权重w（ u，v）指定连接u和v的成本（所需的电线数量）。然后，我们希望找到一个无环子集T，该子集连接所有顶点，并且其总权重w(T)= T中所有权重的总和最小。由于T是无环的并且连接所有顶点，因此它必须形成一棵树，我们称其为a生成树因为它跨越图形ģ。我们称这个问题为最小生成树问题。

MST绿色边缘是MST选定的边缘。

有两种算法可以解决此问题：Kruskal算法和Prim算法。它们每个都以O（E lg V）运行

在这里，我们讨论Kruskal算法...

克鲁斯卡尔算法

该算法首先创建每个顶点的森林，然后根据其权重对边缘进行排序，然后在每个步骤中，在连接两个不属于该森林中同一棵树的不同顶点的树中添加最小权重边缘。

它使用不相交集数据结构来维护几个不相交的元素集。每一组包含当前森林的一棵树中的顶点。

示例：在这里我们发现MST的成本。

程序：

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class MST{
	
	static class set{
		int parent,rank;
	}
	
	//找到代表顶点i的集合
	static int find(set subsets[],int i ){
		if(subsets[i].parent==i)
			return i;
		return find(subsets,subsets[i].parent);
	}
	
	//添加顶点所属的边的功能 
	//到另一棵树，即 联盟
	static void UNION(set subsets[],int x,int y){
		int xroot=find(subsets,x);
		int yroot=find(subsets,y);

		if(subsets[xroot].rank>subsets[yroot].rank)
			subsets[yroot].parent=xroot;
		else if(subsets[xroot].rank<subsets[yroot].rank)
			subsets[xroot].parent=yroot;
		else{
			subsets[yroot].parent=xroot;
			subsets[xroot].rank++;
		}
	}
	
	static int mst(int n, Integer[][] edges) {
		set subsets[]=new set[n];

		//创建vrtices的森林，该森林是每个顶点的单独树
		for(int i=0;i<n;i++)   
		{  
			subsets[i]=new set();
			subsets[i].parent=i;  //每个顶点都是自己的父节点
			subsets[i].rank=0;   //没有子节点 
		}

		int e=0,i=0,count=0;
		//创建完全具有顶点1即的图。n-1条边
		while(e<n-1){
			//找到当前顶点所属的集合
			int x=find(subsets,edges[i][0]-1);  
			//找到当前顶点所属的集合
			int y=find(subsets,edges[i][1]-1); 

			if(x!=y){
				count+=edges[i][2];  
				e++;
				//将两个顶点合并在同一棵树中 
				//如果它们属于不同的集合
				UNION(subsets,x,y); 
			}
			i++;
		}
		return count;
	}

	public static void main(String[] args) 
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();   //节点数
		int m = in.nextInt();  //边数
		Integer [][]edges = new Integer[m][3];
		for(int edges_i = 0; edges_i < m; edges_i++){
			for(int edges_j = 0; edges_j < 3; edges_j++){
				edges[edges_i][edges_j] = in.nextInt();
			}
		}
		
		对二维数组进行排序 
		//其第三列，即权重
		Arrays.sort(edges,new Comparator<Integer[]>(){
			@Override
			public int compare(Integer[] i1,Integer[] i2){
				//比较索引为2的第三列
				return i1[2].compareTo(i2[2]);   
			}
		});
		
		int result=mst(n,edges);
		System.out.println(result);
		in.close();
	}
}

输出结果