本文共 1292 字，大约阅读时间需要 4 分钟。

最小生成树-克鲁斯卡尔算法-Java版（无向图）

关键在于判断是否能够形成环

判断依据：所有的结点都是层层指向最大的结点，如果最后一个相等，说明可以形成环，例如：

1->3->5与4->5可以形成环

package 最小生成树之克鲁斯卡尔算法;class MGraph{	public int[][] arc;	public int vertices;	public MGraph(int n){		vertices = n;		arc = new int[n][n];	}	public void addEdge(int i,int j){		if(i==j){			return;		}		arc[i][j]=1;	}}//主体在于边public class Kruskal {	void MiniSpanTree_Kruskal(MGraph G){		int[] lowcost = new int[G.vertices]; //用来标识是否访问过		int min = Integer.MAX_VALUE;		int row=0,col=0,k=1,m,n;		while(k
   
    ", min,row,col);			if(Find(lowcost,row)
    
     0){			f = lowcost[f];		}		return f;	}	public static void main(String[] args) {		MGraph graph = new MGraph(6);		int[][] temp={
  {65535,6,1,5,65535,65535},                  {6,65535,5,65535,3,65535},                  {1,5,65535,5,6,4},                  {5,65535,5,65535,65535,2},                  {65535,3,6,65535,65535,6},                  {65535,65535,4,2,6,65535}};                 /*int[][] temp={
  {65535,1,2,3,4,65535},                  {1,65535,65535,65535,65535,35},                  {2,65535,65535,65535,8,65535},                  {1,65535,65535,65535,65535,65535},                  {4,65535,8,65535,65535,65535},                  {65535,35,65535,65535,65535,65535}};*/		graph.arc=temp;		new Kruskal().MiniSpanTree_Kruskal(graph);	}}
    
   

转载地址：http://kyonn.baihongyu.com/