Prim 最小生成树 图解

什么是生成树

子图:G=<V,E>,G’=<V’, E’>,为两个图(V为点集,即图中点的集合,E为边集),如果V’是V的子集且E’是E的子集,则G’是G的子图。

如果V’=V,则称G’为G的生成子图

如果G’是无向生成子图且是树的结构,则为生成树

最小生成树

最小生成树:是一张有权无向连通图中边权和最小的生成树

Prme算法:

维护一个已经加入最小生成树的点的集合C,每次通过一条边连接一个不在这个点集C的点,直到最后形成一个树形结构

Dist(u)表示u点到点集C中的点的最小距离

每次选择一个到点集C距离最小的点加入点集C,并通过加入的点去更新未加入的点到点集C的最小距离(因为C中多加了一个点),直到n个点全部加入点集C或没有点能够加入(不能构成连通图)。

图解

《Prim 最小生成树 图解》《Prim 最小生成树 图解》

前言:已经加入点集C的点标记为蓝色,当前加入的点标记为红色,被当前加入的点更新的dist标记为红色。

初始:加入一个初始点A,并通过A更新dist

uABCDEF
dist(u)035infinfinf

加入第二个点B:B到点集C距离最小,并通过B更新dist

uABCDEF
dist(u)03183inf

加入第三个点C:C到点集C距离最小,并通过C更新dist

uABCDEF
dist(u)03183inf

加入第四个点E:E到点集C距离最小,并通过E更新dist

uABCDEF
dist(u)031231

 加入第五个点F:F到点集C距离最小,并通过F更新dist

uABCDEF
dist(u)031231

 加入第六个点D:D到点集C距离最小,并通过D更新dist

uABCDEF
dist(u)031231

 点全部加入点集,Prim算法结束。

复杂度分析:

总共需要加入n个点,每次需要遍历dist数组找最小值,并通过该点更新未加入点集的dist值,即枚举该点连出的边更新对应的dist,故复杂度为:

        O(n*n)+  《Prim 最小生成树 图解》  = O(n*n + m)(mi为每个点连出的边的条数,总和为总边数)

伪代码:

 int prim()

{

    memset(dis, 127, sizeof(dis)); //初始设置为正无穷

    memset(vis, 0, sizeof(vis));   //初始设置点均不在点集中,点集为空

    ans = 0, cnt = 0;              //初始权值为0

    dis[1] = 0;                    // 1加入点集

    while (1)

    {

        int u = -1;

        for (int i = 1; i <= n; i++)

        {

            if (vis[i] == 0 && dis[i] < (1 << 30)) // i点不在点集中并且与点集中的点联通

            {

                if (u == -1 || dis[i] < dis[u]) // u==-1 ->第一个点可以更新到点集最近的点

                {

                    u = i; //更新最近的点

                }

            }

        }

        if (u == -1)

            break;            //如果不能找到加入点集的点,则结束算法

        cnt++, ans += dis[u]; //点集中点的个数+1,ans加上u连入点集的边权

        vis[u] = true;        // vis加入点集

        for (auto it : a[u])//a[u]为以u连出的边的点的集合,v为相连的点,w为边权

        {

            dis[it.v] = min(dis[it.v], it.w); //通过点v连出的边更新不在点集的点的dist值

        }

    }

    if (cnt == n)

        return ans; //能够加入n个点构成连通图,生成树则返回权值

    else

        return -1; //不能形成生成树

}

模板题 

题目链接:最小生成树1 – 题目 – Daimayuan Online Judge

题目描述:

给你一张简单无向连通图,边权都为非负整数。你需要求出它的最小生成树,只需要输出边的权值和即可。

图用以下形式给出:

第一行输入两个整数 n,m,表示图的顶点数、边数,顶点编号从 1 到 n。

接下来 m 行,每行三个整数 x,y,z 表示 x 与 y 之间有一条边,边权为 z。

输入格式:

第一行两个整数 n,m。

接下来 m 行,每行有三个整数,代表一条边。

输出格式:

输出一个数,表示最小生成树的权值和。

数据规模:

对于所有数据,保证 2≤n≤1000,n−1≤m≤100000,1≤x,y≤n,x≠y,1≤z≤10000

样例输入:

4 4

1 2 1

2 3 3

3 4 1

1 4 2

样例输出:

 详见代码:

#include <bits/stdc++.h> using namespace std; int dis[100009], cnt, ans, n, m; // dis为点到点集的最小距离,cnt为点集中点的个数,ans为当前的边权和 bool vis[100009]; struct node { int v, w; }; vector<node> a[100009]; //存图 int prim() { memset(dis, 127, sizeof(dis)); //初始设置为正无穷 memset(vis, 0, sizeof(vis)); //初始设置点均不在点集中,点集为空 ans = 0, cnt = 0; //初始权值为0 dis[1] = 0; // 1加入点集 while (1) { int u = -1; for (int i = 1; i <= n; i++) //遍历找未加入点集的最小距离的点 { if (vis[i] == 0 && dis[i] < (1 << 30)) // i点不在点集中并且与点集中的点联通 { if (u == -1 || dis[i] < dis[u]) // u==-1 ->第一个点可以更新到点集最近的点 { u = i; //更新最近的点 } } } if (u == -1) break; //如果不能找到加入点集的点,则结束算法 cnt++, ans += dis[u]; //点集中点的个数+1,ans加上u连入点集的边权 vis[u] = true; // vis加入点集 for (auto it : a[u]) { dis[it.v] = min(dis[it.v], it.w); //通过点v连出的边更新不在点集的点的dist值 } } if (cnt == n) return ans; //能够加入n个点构成连通图,生成树则返回权值 else return -1; //不能形成生成树 } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; node t1, t2; //无向图存边 t1.v = v, t1.w = w; a[u].push_back(t1); // u->v 边权为w t2.v = u, t2.w = w; a[v].push_back(t2); // v->u 边权为w } cout << prim(); }

《Prim 最小生成树 图解》

 参考文献:

2022 Namomo Spring Camp Div2 Day10 直播课

ending

有什么错误之处欢迎指正!不胜感激!

    原文作者:self_disc
    原文地址: https://www.cnblogs.com/hygge/p/16208980.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞