【最小生成树】(二) Kruskal 算法

题目: 寻宝

题目描述

在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。

不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。

给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿;

提取关键: 存在一些点, 存在一些边, 每条边都有一定的代价, 求将所有点连通的最小代价;

Kruskal 算法

思路

将边按代价从小到大进行排序, 然后从代价最小的开始遍历, 尽量选择代价小的边加入结果集中, 最终使得整个图连通;

当我们遍历到一条边, 这条边所连的两个顶点本身就已经连通时, 那么这条边是多余的, 如果加入, 会产生环;

并查集

并查集的作用与代码在上一篇文章中有详细介绍, 可以到专栏中查看;

前文介绍了并查集的两大作用: 判断两点之间是否连通以及求集合大小; 这里, 介绍另一个用途: 判断无向图中是否存在环;

在无向图中, 如果一条边的两个端点本来就是连通的(处在同一集合中), 那么这个边的加入必然会使得图中产生 “环”
假设图中有 1, 2, 3 三个顶点, 有 [1, 2], [1, 3] 两条边, 现在考虑加入 [2, 3] 这条边, 原本结点 2 和 结点 3 就已经处于连通状态, 现在加入 [2, 3] 必定导致图中出现环状结构;

利用并查集, 就可以在将边纳入[边集]之前进行判断, 判断当前边的加入是否会导致出现环;

1  ____  2\      /\    /3

代码

import java.util.*;public class Main{public static void main(String[] args){kruskal();}// 求最小生成树代价; 对边代价排序, 由小到大连接即可, 连接过程中用 Union 判断环private static void kruskal(){Scanner sc = new Scanner(System.in);int vNum = sc.nextInt();int eNum = sc.nextInt();int[][] edges = new int[eNum][3];for(int i = 0; i < eNum; i++){for(int j = 0; j < 3; j++){edges[i][j] = sc.nextInt();}}Arrays.sort(edges, (e1, e2) -> Integer.compare(e1[2], e2[2]));Union union = new Union(vNum);int res = 0;for(int[] edge : edges){if(!union.isSame(edge[0], edge[1])){res += edge[2];union.join(edge[0], edge[1]);}}System.out.println(res);}
}class Union{private int[] father;public Union(int size){father = new int[size + 1];for(int i = 1; i <= size; i++){father[i] = i;}}public int root(int i){int temp = i;while(father[temp] != temp){temp = father[temp];}father[i] = temp;return temp;}public boolean isSame(int i1, int i2){return root(i1) == root(i2);}public void join(int i1, int i2){father[root(i2)] = root(i1);}
}

上一篇 【最小生成树】(一) 预备知识 并查集