[图论]最小生成树

Prim

注意

• 最好用Prim_Heap，相同条件下更快
• 考虑数据范围，树的重量可能会爆int

说明

• 稀疏图较快
• 找对于到每一个点最近边的长度，存在对应下标的dis数组中

使用方法

1. Prim p;
2. p.init(Vsz, source);初始化顶点个数，起始点位置
3. p.adde(u, v, w);从u指向v权值为w的边，加一次边即可
4. int weight = p.prim();输出最小生成树的重量，无法建成则返回-1

模板

#define Vmax 999
#define INF 0x3f3f3f3f
struct Prim
{
    int n;//n个顶点
    int s;//起点 树的根
    int weight;//树的重量
    int mp[Vmax][Vmax];
    int dis[Vmax]; //dis[i]表示指向i点的最短的边
    bool vis[Vmax];
    int pre[Vmax];//记录前驱

    void init(int Vsz,int source=1)//默认起点为1
    {
        n=Vsz;
        weight=0;
        for(int i=0;i<=n;i++)
        {
            dis[i]=INF;
            vis[i]=false;
        }
        dis[source]=0;
    }

    //1~n的邻接矩阵
    void adde(int u,int v,int w)
    {
        mp[u][v]=w;
        mp[v][u]=w;
    }

    int prim()
    {
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            int pos=0;
            for(int j=1;j<=n;j++)
                if(!vis[j]&&dis[j]<dis[pos])
                    pos=j;
            vis[pos]=true;cnt++;
            weight+=dis[pos];
            for(int j=1;j<=n;j++)
                if(!vis[j]&&mp[pos][j]<dis[j])
                {
                    dis[j]=mp[pos][j];
                    pre[j]=pos;
                }
        }
        if(cnt==n) return weight;
        else return -1;
    }
};

Prim-Heap

使用方法

1. `init(); `
2. mytype ans = prim_heap(s) 得到以s为起点开始找的最小生成树重量
3. judge(n) 判断该树能否生成

模板

typedef int mytype;
const int NV=105;
const int NE=10005*2;
mytype dis[NV];
int pre[NV],vis[NV],he[NV],ecnt,pcnt;

struct edge
{
    int v,next;
    mytype l;
}E[NE];

void adde(int u,int v,mytype l)
{
    E[++ecnt].v=v;
    E[ecnt].l=l;
    E[ecnt].next=he[u];
    he[u]=ecnt;
}

void init(int n,int m,int s)
{
    ecnt=0;
    memset(pre,0,sizeof(pre));
    memset(vis,0,sizeof(vis));
    memset(he,-1,sizeof(he));
    for (int i=0; i<=n; i++)
        dis[i]=inf;
    dis[s]=0;
    for (int i=1; i<=m; i++)
    {
        int u,v;
        mytype l;
        scanf("%d%d%d",&u,&v,&l);
        adde(u,v,l);
        adde(v,u,l);
    }
}

struct point
{
    int u;
    mytype l;
    point(int u,mytype l):u(u),l(l){}
    bool operator<(const point &p) const
    {
        return l>p.l;
    }
};

mytype prim_heap(int s)
{
    priority_queue<point> q;
    q.push(point(s,0));
    mytype ans=0;
    pcnt=0;
    while(!q.empty())
    {
        point p=q.top();
        q.pop();
        int u=p.u;
        if (vis[u])
            continue;
        vis[u]=1;
        ans+=p.l;//==dis[x]
        pcnt++;
        for(int i=he[u]; i!=-1; i=E[i].next)
            if(!vis[E[i].v]&&E[i].l<dis[E[i].v])
            {
                dis[E[i].v]=E[i].l;
                pre[E[i].v]=u;
                q.push(point(E[i].v,dis[E[i].v]));
            }
    }
    return ans;
}

bool judge(int n)
{
    return pcnt==n;
}

Kruskal

说明

1. 结构体排序＋并查集———结构体排序找到所有符合条件的边，加入并查集
2. 稀疏图较快

使用方法

1. `Kruskal d; `
2. d.init(Vsz,Esz); 初始化顶点个数，边的个数
3. d.adde(u,v,w); 从u指向v权值为w的边，单向加边即可
4. int weight = d.kruskal();输出最小生成树的重量，无法建成则返回-1

模板

#define Vmax 300 //最大点数量
#define Emax 1000 //最大边数量
struct Kruskal
{
    int n,m;//n个点 m条边
    int rank[Vmax],fa[Vmax];//并查集需要
    int weight;// weight为最小生成树的重量
    int ecnt;
    struct edge
    {
        int u,v,w;//起点 终点 权值
        bool operator<(const edge e) const{return w<e.w;}
    }e[Emax];

    void init(int Vsz,int Esz)
    {
        n=Vsz;m=Esz;
        ecnt=0;
        weight=0;
        for(int i=0;i<=Vsz;i++)
        {
            fa[i]=i;
            rank[i]=0;
        }
    }
    //边的编号从0～m-1

    void adde(int u,int v,int w)
    {
        e[ecnt].u=u;
        e[ecnt].v=v;
        e[ecnt++].w=w;
    }

    int findx(int x)
    {
        while(x!=fa[x])
        x=fa[x];
        return x;
    }

    void set_merge(int u,int v)
    {
        if(rank[u]<rank[v])
        {
            fa[u]=v;
            rank[v]+=rank[u];
        }
        else
        {
            fa[v]=u;
            rank[u]+=rank[v];
        }
    }

    int kruskal()
    {
        int cnt=0;
        sort(e,e+m);
        for(int i=0;i<m;i++)
        {
            int uR=findx(e[i].u);
            int vR=findx(e[i].v);
            if(uR!=vR)
            {
                set_merge(uR, vR);
                weight+=e[i].w;
                cnt++;
            }
        }
        if(cnt==n-1) return weight;//最小生成树可建
        else return -1; //最小生成树不可建
    }
};