图的最小生成树kruskal算法总结

谁借莪１个温暖的怀抱￠ 2022-09-29 01:47 153阅读 0赞

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（）方法我们可以找到该顶点所在连通分量的根顶点，如果两个顶点的根顶点相同，则代表这两个顶点在同一个连通分量上，反之则不是。

## **算法运行详解**    ##

**1**.用边集数组存储图，然后再按照权值大小进行非递减排好序，结果如下图所示

![Center][]

**2.**初始化parent\[\],结果如下图

![Center 1][]

值全部为0也就代表每一个顶点自称一个连通分量

**3.**取权值最小的边

**4.**调用find方法得到顶点所在连通分量的根顶点

注：其实每个连通分量的全部顶点可以看成类似树，但此树的边总是从子结点指向父节点，最后树的根即为根顶点,

如当循环到edges\[6\]时，有如下图所示结果

![Center 2][]

如上图所示，通过parent\[\]数组可以画出两个类似树的连通分量，其中7和6分别为森林中两个不同的连通分量的根顶点。如要判断顶点5所在连通分量的根顶点是什么，图中可看到5的父结点为8,8的父节点为6,6的父结点为空，说明6即为连通分量的根节点。

**5.**如果两个顶点的根顶点不同，说明两个顶点在不同的连通分量上，将该边加入最小生成树中，否则舍弃。

**6.**取最小权值的边不断循环......

[Center]: /images/20220708/b4be3d3dd4cc42fdb6fe0be63f0a65b0.png
[Center 1]: /images/20220708/1aaa6e0f2bef455a884440804bc7a51f.png
[Center 2]: /images/20220708/4ca95fb1380f4c82aea3d6f0bbe8a3a8.png