Kruskal
思路
贪心思想,将所有边进行排序,依次连接。利用UF判断亮点连通性,若2点已经连通,则跳过,避免成环。
实现
class Solution {
public int minimumCost(int n, int[][] connections) {
int cost = 0;
Arrays.sort(connections, (x, y) -> x[2] - y[2]);
UF uf = new UF(n);
for (int[] connection: connections) {
if (uf.conntected(connection[0] - 1, connection[1] - 1))
continue;
cost += connection[2];
uf.union(connection[0] - 1, connection[1] - 1);
}
return uf.count() == 1? cost: -1;
}
}
class UF {
private int count;
private int[] parent;
public UF(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++)
parent[i] = i;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
count--;
}
public boolean conntected(int p, int q) {
return find(p) == find(q);
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public int count() {
return count;
}
}
Prim
思路
每次将一个图切成2个连通分量,那么总有一条边是最小生成树的边。找到其中最小的边,加入即可。同时,将此边对应的新加入节点的边都加入候选。
为了避免成环,需要一个visited数组记录所有点的访问情况,若已访问则跳过。