寒假训练报告1.31（最小生成树）

前提条件：生成树是否存在 <=> 图是否连通

1.Prim算法（加点法）

适用范围：稠密图

算法描述：从只包含一个顶点v的树T，贪心地选取T和其他顶点之间相连的最小权值的边，并把它加到T中。

查找最小权值的边：把X和顶点V连接的边的最小权值记为mincost[v]，向X添加顶点u时，查看和u相连的边，对于每条边，更新mincost[v] = min( mincost[v], e[u][v])

时间复杂度：每次都遍历未包含在X中的点的mincost[v]，O(|V|^2)，使用堆维护为O(|E|log|V|)

int mp[maxn][maxn]; //边e=(u,v)的权值
int dis[maxn];  //从集合X出发的边到每个顶点的最小权值
bool vis[maxn]; //顶点i是否包含在集合X中
void Prim(){
    fill(vis, vis + n, );
    fill(dis, dis + n, INF);
    dis[] = ;
    int ans = ;
    while(true){
        int v = -;
        //从不属于X的顶点中选取从X到其权值最小的顶点
        for(int u = ; u < n; u++)
            if(!vis[u] && (v == - || dis[u] < dis[v]))
                v = u;
        if(v == -)  break;
        vis[v] = ; //把顶点v加入X
        ans += dis[v];  //把边的长度加到结果里
        for(int u = ; u < n; u++)
            dis[u] = min(dis[u], mp[v][u]);
    }
    return ans;
}
           

2.Kruskal算法（加边法）

适用范围：稀疏图

算法描述：按照边的权值的顺序从小到大查看一遍，如果不产生圈（或重边），就把当前边加入到生成树中。

判断是否产生圈：使用并查集高效地判断是否属于同一个连通分量。

时间复杂度：排序最费时，O(|E|log|V|)

struct edge{
    int u, v, cost;
}s[maxn];
bool cmp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}
int V, E;   //顶点数和边数
int Kruskal(){
    sort(s, s + E, cmp);
    Init(V);    //并查集的初始化
    int ans = ;
    for(int i = ; i < E; i++){
        edge e = s[i];
        if(!same(e.u, e.v)){
            Union(e.u, e.v);
            ans += e.cost;
        }
    }
    return ans;
}
           

例题

POJ 3723

求征募人员关系之间的最大值

无向图最大权森林问题，可以将所有边权取反之后用最小生成树Kruskal的问题求解。