最小生成树

· · 算法·理论

NO.1 kruscal

这是一个样例：

首先 我们要把所有边的长度按长度从小到大排列，如下

1 2 2
1 3 2
1 4 3
3 4 3
2 3 4

从前往后枚举. 每一次 如果一条边的两个点不在一个合集里面 就将两点加入 就得到了如下：

示例代码

bool cmp(node a,node b) {
    return a.w<b.w;
}
int find(int x){//并查集
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
bool kruscal(){
    int cut=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(l+1,l+m+1,cmp);
    for(int i=1;i<=m;i++){
        int A=find(l[i].x),B=find(l[i].y);
        if(A!=B){//不在一个集合里
            fa[A]=B;
            ans+=l[i].w;
            cut++;
        }
        if(cut==n-1) return 1;//最小树算完
    }
    return 0;
}

NO.2 prim

一样的样例：

按照点来枚举，每一次寻找那个点距离已经确认好的最小生成树最近的一条边 ，并连接。 最终也能得到相同的结果：

示例代码

void add(int x,int y,int z){
    ver[++tot]=y,edg[tot]=z;
    nxt[tot]=head[x],head[x]=tot;
}
bool prim(){
    priority_queue< PII,vector<PII>,greater<PII> > Q;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;Q.push({0,1});
    while(!Q.empty()){
        int x=Q.top().second,ds=Q.top().first;Q.pop();
        if(vis[x]) continue;vis[x]=1;
        ans+=ds,cnt++;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i],w=edg[i];
            if(dis[y]>w){
                dis[y]=w;
                Q.push({w,y});
            }
        }
    }
    return cnt==n;
}