kruskal算法的思想
假如N={V,{E}}是连通网，那么最小生成树的初始状态是由V个顶点自成连通分量构成的一片森林。在E中选择权值最小的边，当该边对应的两个顶点在不同分量时，则将该边加入到最小生成树中，否则的舍去，再选择下一条代价最小的边，如此循环，直到所有的连通分量连接变成一个连通分量为止。
看看具体代码
public void minSpanTree_kurskal(Edges[] edges){ //edges已按照权值大小进行了非递减排序 Integer parent[] = new Integer[edges.length]; int n,m; for(int i=0;i<edges.length;i++){ //初始化parent[]全部元素为0; parent[i] = 0; } for(int i=0;i<edges.length;i++){ n = find(parent,edges[i].begin); //寻找edges[i].begin所在连通分量的根顶点 m = find(parent,edges[i].end); //寻找edges[i].end所在连通分量的根顶点 if(n!=m){ // 如果根结点不同说明dges[i].begin和dges[i].end在不同分量上 parent[n] = m; System.out.println("begin="+edges[i].begin+","+"end="+edges[i].end+","+"weight="+edges[i].weight); } } } private int find(Integer[] parent, int f) { while(parent[f]>0) f = parent[f]; return f; }
这里存在一个问题：如何判断2个顶点在同一个连通分量？
每个连通分量上都有一个顶点代表整个连通分量，我们把它叫做根顶点，也就是通过find（）方法我们可以找到该顶点所在连通分量的根顶点，如果两个顶点的根顶点相同，则代表这两个顶点在同一个连通分量上，反之则不是。
2.初始化parent[],结果如下图
值全部为0也就代表每一个顶点自称一个连通分量
3.取权值最小的边
4.调用find方法得到顶点所在连通分量的根顶点
注：其实每个连通分量的全部顶点可以看成类似树，但此树的边总是从子结点指向父节点，最后树的根即为根顶点,
如当循环到edges[6]时，有如下图所示结果
如上图所示，通过parent[]数组可以画出两个类似树的连通分量，其中7和6分别为森林中两个不同的连通分量的根顶点。如要判断顶点5所在连通分量的根顶点是什么，图中可看到5的父结点为8,8的父节点为6,6的父结点为空，说明6即为连通分量的根节点。
5.如果两个顶点的根顶点不同，说明两个顶点在不同的连通分量上，将该边加入最小生成树中，否则舍弃。
6.取最小权值的边不断循环......
