最小生成树代码存档 -prim 和 kruskal

最小生成树代码存档，基于《算法笔记》中的代码，方便以后查看使用。

prim 算法

伪代码

//G 为图，一般设成全局变量，数组 d 为顶点与集合 s 的最短距离
Prim(G,d[]){
    初始化;
    for(循环 n 次){
        u= 使 d[u] 最小的未被访问的顶点的标号;
        记 u 已被访问;
        for(从 u 出发能够到达的所有顶点 v){
            if(v 未被访问 && 以 u 为中介点使得 v 与集合 s 的最短距离 d[v]更优){
                将 G[u][v]赋值给 v 与集合 s 的最短距离 d[v];
            }
        }
    }
}

邻接数组代码

int n,G[MAXN][MAXN]; //n 为顶点数，MAXN 为最大顶点数
int d[MAXN]; // 顶点与集合 s 的最短距离
bool vis[MAXN]={false}; // 标记数组，vis[i]==true 表示已访问。初值为 false

int prim(){ // 默认 0 号为初始点，函数返回最小生成树的边权之和
    fill(d,d+MAXN,INF); //fill 函数将整个 d 数组赋为 INF（慎用 memset）
    d[0]=0; // 只有 0 号顶点到集合 s 的距离为 0，其余全为 INF
    int ans=0 // 存放最小生成树的边权之和
    for(int i=0;i<n;i++){ // 循环 n 次
        int u=-1,MIN=INF; //u 使 d[u] 最小,MIN 存放该最小的 d[u]
        for(int j=0;j<n;j++){ // 找到未访问的顶点中 d[]最小的 
            if(vis[j]==false && d[j]<MIN){
                u=j;
                MIN=d[j];
            }
        }

        // 找不到小于 INF 的 d[u]，则剩下的顶点和集合 s 不连通
        if(u==-1) return -1;
        vis[u]=true; // 标记 u 为已访问
        ans+=d[u]; // 将与集合 s 距离最小的边加入生成树
        for(int v=0;v<n;v++){
            //v 未访问 && u 能到达 v && 以 u 为中介点可以使 v 离集合 s 更近
            if(vis[v]==false && G[u][v] != INF && G[u][v]<d[v]){
                d[v]=G[u][v]; // 将 G[u][v] 赋值给 d[v]
            }
        }  
    }
    return ans;
}

邻接表代码

struct Node{
    int v,dis; //v 为边的目标顶点，dis 为边权
};
vector<Node> Adj[MAXN]; // 图 G，Adj[u] 存放从顶点 u 出发的可以到达的所有顶点 
int n; //n 为顶点数，图 G 使用邻接表实现，MAXN 为最大顶点数
int d[MAXN]; // 顶点与集合 s 的最短距离
bool vis[MAXN]={false}; // 标记数组，vis[i]==true 表示已访问。初值为 false

int prim(){ // 默认 0 号为初始点，函数返回最小生成树的边权之和
    fill(d,d+MAXN,INF); //fill 函数将整个 d 数组赋为 INF（慎用 memset）
    d[0]=0; // 只有 0 号顶点到集合 s 的距离为 0，其余全为 INF
    int ans=0 // 存放最小生成树的边权之和
    for(int i=0;i<n;i++){ // 循环 n 次
        int u=-1,MIN=INF; //u 使 d[u] 最小,MIN 存放该最小的 d[u]
        for(int j=0;j<n;j++){ // 找到未访问的顶点中 d[]最小的 
            if(vis[j]==false && d[j]<MIN){
                u=j;
                MIN=d[j];
            }
        }

        // 找不到小于 INF 的 d[u]，则剩下的顶点和集合 s 不连通
        if(u==-1) return -1;
        vis[u]=true; // 标记 u 为已访问
        ans+=d[u]; // 将与集合 s 距离最小的边加入生成树

        // 只有下面这个 for 与邻接矩阵写法不同
        for(int j=0;j<Adj[u].size();j++){
            int v=Adj[u][j].v;
            if(vis[v]==false && Adj[u][j].dis<d[v]){
                // 如果 vw 未访问 && 以 u 为中介点可以使 v 离集合 s 更近
                d[v]=G[u][v]; // 将 G[u][v] 赋值给 d[v]
            }
        }  
    }
    return ans;
}

kruskal 算法

伪代码

int kruskal(){
    令最小生成树的边权之和为 ans、最小生成树的当前边数 Num_Edge;
    将所有边按边权从小到大排序;
    for(从小到大枚举所有边){
        if(当前测试边的两个端点在不同的连通块中){
            将该测试边加入最小生成树中;
            ans += 测试边的边权;
            最小生成树的当前边数 Num_Edge 加1;
            当边数 Num_Edge 等于顶点数减1 时循环结束;
        }
    }
    return ans;
}

代码

// 边集定义部分
struct edge{
    int u,v; // 边的两个端点编号
    int cost; // 边权
}E[MAXE]; // 最多有 MAXE 条边
bool cmp(edge a,edge b){
    return a.cost<b.cost;
}

// 并查集部分
int father[MAXN];
int findFather(int x){
    if(x!=father[x])
        return father[x]=findFather(father[x]);
    return x;
}

//kruskal 部分，返回最小生成树的边权之和，参数 n 为顶点个数，m 为图的边数
int kruskal(){
    int ans=0,Num_Edge=0;
    for(int i=0;i<n;i++){
        father[i]=i;
    }

    sort(E,E+m,cmp);

    for(int i=0;i<m;i++){
        int faU=findFather(E[i].u);
        int faV=findFather(E[i].v);
        if(faU!=faV){
            father[faU]=faV;
            ans+=E[i].cost;
            Num_Edge++;
            if(Num_Edge==n-1)break;
        }
    }

    if(Num_Edge!=n-1) return -1;
    return ans;
}

简化版代码（based on leetcode1584）

const int MAXN = 1000 + 50;
int fa[MAXN];

int getFather(int x){
    if (fa[x] == x) return x;
    return fa[x] = getFather(fa[x]);
}

bool mergeFather(int x, int y){
    int fx = getFather(x), fy = getFather(y);
    if (fx == fy) return false;
    if (fx > fy) swap(fx, fy);
    fa[fx]= fy;
    return true;
}

struct Edge{
    int x, y, w;
    Edge(){}
    Edge(int x0, int y0, int w0){ x = x0; y = y0; w = w0; }
}edge[MAXN * MAXN];

bool cmp(const Edge &a, const Edge &b){ return a.w < b.w; }

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), m = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                edge[m++] = Edge(i, j, abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]));
        sort(edge, edge + m, cmp);

        for (int i = 0; i < n; i++) fa[i] = i;

        int ans = 0, cnt = n;
        for (int i = 0; i < m && cnt > 1; i++){
            int x = edge[i].x, y = edge[i].y, w = edge[i].w;
            if (mergeFather(x, y)){ ans += w; --cnt; }
        }
  
        return ans;
    }
};