最小生成树及应用

linno 2021-08-15 原文

title : 最小生成树
date : 2021-7-30
tags : ACM,图论

最小生成树(MST)

什么是最小生成树问题？

我们给n个点m条边，选出n-1条边把所有点连起来（默认只有一块），使得边权之和最小，这就是最小生成树(Minimum Spanning Tree)问题。

该问题有两种比较常见的作法：kruskal和Prim

Kruskal

步骤

基于贪心思想，先把边从小到大排列，然后按顺序选边并且合并每条边相连的两点所在集合（若两点处于同一集合内，则该边不必再选），直到所有点处于同一集合为止。

前置知识

并查集

代码模板

    sort(e+1,e+1+cnt); //按边权从小到大排序 
    for(int i=1;i<=cnt;i++){
        int u=e[i].from,v=e[i].to;
        if(find(u)!=find(v)){ //Kruskal算法，找到未合并的两点合并 
            unite(u,v);
            mx=e[i].dis; //更新最大边 
            num++;
            sum+=e[i].dis;
        }
        if(num==n-1) break; //可以在连了n-1条边时即使跳出 
    }

Prim算法

步骤

从任意顶点开始，选择一个与当前顶点最近的一个顶点，连接两顶点的边加入集合中，然后将两顶点合并成一个点。重复上述操作至点都合并到了一个集合中。

代码模板


int prim(int graph[][MAX], int n)
{
    int lowcost[MAX];
    int mst[MAX];
    int i, j, min, minid, sum = 0;
    for (i = 2; i <= n; i++)
    {
        lowcost[i] = graph[1][i];
        mst[i] = 1;
    }
    mst[1] = 0;
    for (i = 2; i <= n; i++)
    {
        min = MAXCOST;
        minid = 0;
        for (j = 2; j <= n; j++)
        {
            if (lowcost[j] < min && lowcost[j] != 0)
            {
                min = lowcost[j];
                minid = j;
            }
        }
        cout << "V" << mst[minid] << "-V" << minid << "=" << min << endl;
        sum += min;
        lowcost[minid] = 0;
        for (j = 2; j <= n; j++)
        {
            if (graph[minid][j] < lowcost[j])
            {
                lowcost[j] = graph[minid][j];
                mst[j] = minid;
            }
        }
    }
    return sum;