图论-最小生成树

深碍√TFBOYSˉ_ 2022-05-28 04:51 136阅读 0赞

给定一个无向图，如果它的某一个子图中任意俩个顶点都互相联通并且是一棵树，那么这棵树就是生成树。如果边上还有权值，边权和最小的称为最小生成树。

算法1：Prim算法

算法操作：首先，我们假设有一棵只包含顶点v的树T,然后贪心地选取和其他顶点之间相连的最小权值的边，并把它加到T中，不断操作就可以得到最小生成树。

时间复杂度：O（V\*V)

代码如下:

const int inf=0x3f3f3f3f;
    const int maxn=150;
    int G[maxn][maxn];//存图
    int mincost[maxn];
    bool vis[maxn];
    
    int Prim(int V)
    {
        for (int i=0;i<V;i++) {
            mincost[i]=inf;
            vis[i]=false;
        }
        mincost[0]=0;
        int ans=0;
        while (true) {
            int v=-1;
            for (int i=0;i<V;i++) {
                if (!vis[i]&&(v==-1||mincost[i]<mincost[v])) v=i;//找下一个顶点
            }
            if (v==-1) break;
            vis[v]=true;
            ans+=mincost[v];
            for (int j=0;j<V;j++) {
                mincost[j]=min(mincost[j],G[v][j]);//更新
            }
        }
        return ans;
    }

算法2：Kruskal算法

算法操作：Kruskal算法的操作对象是边，把所有的边按照权值重新到大排序，然后对每一条边的俩个端点，用并查集检查一下是否已经连起来了。

并查集可以高效的判断是否属于同一个联通分量

时间复杂度:O（ElogV)

代码如下:

const int maxn=150;
    struct ege{
        int from,to,cost;
    };
    vector<ege> es;
    int pre[maxn];
    
    bool cmp(ege a,ege b)
    {
        return a.cost<b.cost;
    }
    /* 并查集*/
    void init(int n)
    {
        for (int i=0;i<n;i++) {
            pre[i]=i;
        }
    }
    int find(int x)
    {
        if (pre[x]==x) return x;
        else {
            int ans=find(pre[x]);
            return pre[x]=ans;
        }
    }
    void join(int x,int y)
    {
        int fx=find(x);
        int fy=find(y);
        if (fx!=fy) pre[fx]=fy;
    }
    
    int Kruskal(int V)
    {
        sort(es.begin(),es.end(),cmp);
        init(V);
        int ans=0;
        for (int i=0;i<es.size();i++) {
            ege e=es[i];
            if (find(e.from)!=find(e.to)) {
               ans+=e.cost;
               join(e.from,e.to);
            }
        }
        return ans;
    }