Kruskal算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class UF{
public:
    vector<int>fa;
    vector<int>rank;
    int n;
    int comp_cnt;
public:
    UF(int _n): n(_n), comp_cnt(_n), fa(_n), rank(_n, 1){
        iota(fa.begin(),fa.end(),0);
    }
    int find(int x){
        //cout << "find" << endl;
        return x==fa[x] ? x:(fa[x] = find(fa[x]));
    }
    void merage(int i ,int j){
        int x = find(i), y = find(j);
        //cout << "merage" <<endl;
        if (rank[x]<=rank[y])
            fa[x] = y;
        else
            fa[y] = x;
        if(rank[x] == rank[y] && x!=y){
            rank[y]++;
        }
        if (x!=y)
            comp_cnt--;
    }
    bool connected(int x,int y){
        return find(x) == find(y);
    }
};
struct Edge{
    int u , v , w;
    Edge(int _u, int _v , int _w): u(_u),v(_v),w(_w){}
    bool operator <(const Edge & that){
        return w < that.w;
    }
};
class Solution {
public:
    int toweight(vector<int>& a ,vector<int> &b){
        return abs(a[0]-b[0]) + abs(a[1] - b[1]);
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        //Kruskal算法，需要结合并查集来操作
        int len = points.size();
        vector<Edge>edges;
        for(int i = 0; i < len; ++i){
            for(int j = i+1; j < len; ++j){
                edges.emplace_back(i,j,toweight(points[i],points[j]));
            }
        }
        UF uf(len);
        sort(edges.begin(),edges.end());
        int ans = 0;
        for(auto &edge:edges){
            int u = edge.u, v = edge.v, w= edge.w;
            if(!uf.connected(u,v)){
                uf.merage(u,v);
                ans+=w;
            }
            if(uf.comp_cnt == 1){//当只剩下一个集合的时候就结束
                break;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
*
    * Prim 求 MST
    * 耗费矩阵 cost[][]，标号从 0 开始，0∼n-1 
    * 返回最小生成树的权值，返回 -1 表示原图不连通
    */
    const int INF=0x3f3f3f3f;
const int MAXN=110;
bool vis[MAXN];
int lowc[MAXN];
//点是 0 n-1
int Prim(int cost[][MAXN],int n){
    int ans=0;
    memset(vis,false,sizeof(vis));
    vis[0]=true;
    for(int i=1;i<n;i++)lowc[i]=cost[0][i];
    for(int i=1;i<n;i++){
        int minc=INF;
        int p=−1;
        for(int j=0;j<n;j++)
            if(!vis[j]&&minc>lowc[j]){
                minc=lowc[j];
                p=j;
            }
        if(minc==INF)return −1;//原图不连通
        ans+=minc;
        vis[p]=true;
        //将以p为顶点的边加入lowc[j]
        for(int j=0;j<n;j++)
            if(!vis[j]&&lowc[j]>cost[p][j])
                lowc[j]=cost[p][j];
    }
    return ans;
}