生成树-Kruskal & Prim

最小生成树

最小生成树是指，对于一个连通图，剔除其中一部分边，而保留一部分边，使得剩下的部分构成一棵树，并且这棵树的所有便的权值之和最小。

最小生成树所处理的图的边权一般是不相等的，否则意义不大。

常见的求最小生成数的算法Kruskal算法和Prim算法

Kruskal算法

Kruskal算法基于贪心的想法

1.将所有边按照边权排序（如若不懂边权，可查看上一篇）

2.从小到大遍历所有边（x,y），如果(x,y)已经连通就跳过，否则就选中，将它两相连。

在第二步中的连通性判断需要用到并查集。

int n=scan.nextInt();
int m=scan.nextInt();
father=new int[n+1];
for(int i=0;i<=n;i++){
    father[i]=i;
}
int max=0;
List<int []> list=new ArrayList<>();
for(int i=0;i<m;i++){
    int x=scan.nextInt();
    int y=scan.nextInt();
    int z=scan.nextInt();
    list.add(new int[] {x,y,z});
}
Collections.sort(list,(o1,o2)->o1[2]-o2[1]);
for(int i=0;i<m;i++){
    int x=find(list.get(list.get(i)[0]));//并查集的find方法
    int y=find(list.get(i)[1]);
    if(x!=y){
//x,y没有被连接起来
        union(x,y);//并查集的连接方法
        max=Math.max(max,list.get(i)[2]);
    }
}
System.out.println(max);

Prim算法

Prim算法采用集合的思想，维护一个vis数组，里面存储已经在最小生成树中的点。

1：从起点（一般为1号点）出发，每次找出不在vis中且d最小的点x,d就是选中的那条便的边权

2：将点x加入到vis中，并更新其所有出点y，更新d[y]=min(d[y],w);//w为x->y的距离为3.如果d[y]b变小了，就加入到优先队列中作为可能的拓展点。

这个vis我们用boolean数组实现即可，写法类似，只有d数组的区别：Diikstra算法中d[x]表示x到原点的最短距离。Prim算法中d[x]表示x到集合vis中任意一点的最短距离。

int m=scan.nextInt();
List<int[]>[] list=new List[n+1];
//建立连接表存储我们的图
for(int i=0;i<n;i++){
    list[i]=new ArrayList<>();
}
int max=0;
PriorityQueue<int[]> q=new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
//优先队列，从小到大
int[] d=new int [n+1];
boolean[] vis=new boolean[n+1];
//利用vis维护我们的集合
for(int i=0;i<m;i++){
    int x=scan.nextInt();
    int y=scan.nextInt();
    int z=scan.nextInt();
    list[x].add(new int[] {y,z});
    list[y].add(new int[] {x,z});

}
Arrays.fill(d,(int) le9);
d[1]=0;
q.add(new int[] {1,0});
while(!q.isEmpty()){
    int[] a=q.poll();
    if(vis[a[0]]){
        continue;
//已经存在跳过
    }
    vis[a[0]]=true;
    max=Math.max(d[b[0]],b[1]);
    for(int[] b:list[a[0]]){
        d[b[0]]=Math.min(d[b[0]],b[1]);
        q.add(new int[] { b[0],d[b[0]] });
    }
}

例题

蓝桥公司的一个推销员要买新车帮助它的工作，但它必须决定新车油箱的容量，假设这两新车每公里耗油一升。

每个城市至少有一个加油站，推销员可以在那里加油，但城市之间的道路没有加油站，给出城市及其之间道路的描述，找出所需油箱的最小容量，以便推销员能够至少以一种方式在任何一对城市之间旅游。

输入格式

输入的第一行包含两个整数：N和M，其中N为城市数量，M为道路数量

以下M行包含三个整数：X,Y,C，其中C是城市X，和城市Y之间的长度，单位为公里，道路可以双向使用。

题目保证每对城市之间最多有一条道路相连，并且可以使用给定的道路在任意一对城市之间旅行。

输出格式

对于每个测试用例，打印一行整数表示油箱所需的最小容量。