公众号merlinsea
- 问题介绍
- 已知一个无向带权图，现在希望求出保证这个无向带权图连通性同时是的所有遍的权重之和最小的连通子图。
- 最小生成树问题介绍
- 现在有一个无向带权图，请求出这个图的最小生成树。
- 最小指的是基于原图得到的树的边的权值之和是最小的。
- 树指的是保证图中所有节点连通的无回路的图。
- 算法难点： 如何才能快速判断是否存在回路呢？
- 并查集的介绍
- 树是保证所有节点连通且没有回路的极大连通子图，在树中的任意两个节点之间多加入一条边，那么就会产生回路。
- 并查集就是把这些节点看成一个树，并且采用树的双亲存储，如果我们加入一条新的边，边的两个端点节点都在同一棵树中，那么这两个节点之间加入边就会产生回路。
- 克鲁斯卡尔代码实现
public class Main { public static void main(String[] args) { // {0,1,5}表示j节点0，1之间有一条权重为5的边 int[][] edges = new int[][]{{0,1,5},{0,2,1},{0,3,2},{1,2,3},{2,3,6},{1,4,4},{2,4,2},{3,4,3}}; int n = 5; Arrays.sort(edges, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { //升序排列，返回正数就发生交换 return o1[2]-o2[2]; } }); for(int[] edge : edges){ System.out.println("["+ edge[0]+" "+ edge[1] + " " + edge[2] +"]"); } System.out.println(); //树的双亲存储 int[] tree = new int[n]; for(int i=0;i<n;i++){ tree[i] = i; } List<int[]> result = new LinkedList<>(); int i = 0; // cnt 代表我们选取的边的个数 int cnt = 0; while(cnt<n-1){ int a = edges[i][0]; int b = edges[i][1]; int aPar = findPar(tree,a); int bPar = findPar(tree,b); if(aPar != bPar){ //说明a，b不属于同一棵树 ,因此加入<a，b>边不会产生回路 result.add(edges[i]); //链接 bPar 和 aPar tree[aPar] = bPar; //选取的边+1 cnt++; } i++; } for(int j=0;j<result.size();j++){ int[] edge = result.get(j); System.out.println("["+ edge[0]+" "+ edge[1] + " " + edge[2] +"]"); } } /** * 查找双亲节点 */ public static int findPar(int[] tree,int k){ if(tree[k]==k){ return k; } tree[k] = findPar(tree,tree[k]); return tree[k]; } }
- 算法性能分析
- 从上面的代码中可以发现，克鲁斯卡尔算法的时间开销主要是sort()排序上，在之前的排序算法中，我们知道排序的最快时间复杂度是O(nlogn)，而我们排序其实是对所有的边进行排序的，所以对于边越少的图，越适用于通过克鲁斯卡尔算法生成最小生成树。
- 最小生成树问题的应用场景
- 比如村村通路问题：假设有若干个村庄，现在政府需要为这些村子进行修路，现在已经知道了每个村庄相互之间的距离，并且修路的费用成本和路之间的距离成正比关系，问如何修路才能保证个村庄可以相互连通的基础上尽可能让市政的投入的费用最小？
