Prim 最小生成树(图解)

这篇具有很好参考价值的文章主要介绍了Prim 最小生成树(图解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

什么是生成树

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

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

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

最小生成树

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

Prim算法:

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

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

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

图解

Prim 最小生成树(图解)

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

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

u A B C D E F
dist(u) 0 3 5 inf inf inf

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

u A B C D E F
dist(u) 0 3 1 8 3 inf

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

u A B C D E F
dist(u) 0 3 1 8 3 inf

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

u A B C D E F
dist(u) 0 3 1 2 3 1

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

u A B C D E F
dist(u) 0 3 1 2 3 1

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

u A B C D E F
dist(u) 0 3 1 2 3 1

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

复杂度分析:

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

        O(n*n)+    = 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();
}

 参考文献:

2022 Namomo Spring Camp Div2 Day10 直播课

ending

有什么错误之处欢迎指正!不胜感激!文章来源地址https://www.toymoban.com/news/detail-493385.html

到了这里,关于Prim 最小生成树(图解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 最小生成树——prim算法实现

    N个城市之间需要铺设一张交通网,使任意两个城市间都有交通路线直达,现已知各个城市之间铺设道路的经济成本,问该如何求算铺网的最低经济成本?为求算最低经济成本,可以假设N个城市就是连通网G的N个顶点,而求算最低成本问题可以转化为在N个城市间找到N-1条边,

    2024年02月08日
    浏览(38)
  • Prim算法实现最小生成树

    例如:要在n个城市之间铺设光缆,主要目标是要使这n个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。 将图中所有顶点分为两类:树顶点(已

    2024年02月11日
    浏览(43)
  • 最小生成树——普利姆(Prim)算法

    构成连通网的最小代价生成树称为最小生成树(Minimun Cost Spanning Tree). 最小生成树可以运用到生活中,假如你是一位工程师,需要为一个镇的九个村庄架设通信网络做设计,村庄位置大值如下图:  其中 V0~V8 是村庄,之间连线的数字表示村与村间的可通达的直线距离,比如

    2024年02月04日
    浏览(43)
  • 图的最小生成树-Prim算法

    目录 问题引入  程序设计  程序分析 本节文章 【问题描述】 编写程序,利用带权无向图的邻接矩阵存储,实现图的最小生成树Prim算法。 【输入形式】 输入图的顶点序列及图的边的情况。如样例所示。边的输入以输入-1,-1,-1,作为结束。 0,1,6 表示对应的顶点及边是:

    2024年02月08日
    浏览(53)
  • 贪心算法:最小生成树Prim算法

    👨‍🎓作者简介:一位喜欢写作,计科专业大二菜鸟 🏡个人主页:starry陆离 🕒首发日期:2022年5月31日星期二 🌌上期文章:动态规划:多重背包问题 📚订阅专栏:算法分析与设计 如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦 这是大一暑假的c笔记,再一次写pri

    2024年02月01日
    浏览(52)
  • 最小生成树Prim算法详解(C++)

    Prim算法是一种用于寻找加权无向图的最小生成树的贪心算法。它的基本思路是从图中任意一个点开始,选择与该点相邻的最小边,并将该边所连接的点加入到生成树的集合中。然后再从新加入的点出发,重复该过程直到所有的节点都被加入到生成树中。 初始化:首先需要初

    2024年02月11日
    浏览(39)
  • 最小生成树(Prim算法,Kruskal算法)

    (1)生成树: 如果在一个无向连通图不包含回路(连通图中不存在环),则为一个树 (2)最小生成树(minimal spanning tree): 在一个图所有生成树中,代价最小的生成树称为最小生成树 (3)生成树的代价: 在一个无向连通网中,生成树各边的权值之和称为该生成树的代价

    2024年02月08日
    浏览(45)
  • 最小生成树—Kruskal算法和Prim算法

    连通图:在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中任 意一对顶点都是连通的,则称此图为连通图。 生成树:一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点 和n-1条边。 最小生成树:构成生成树的

    2024年02月05日
    浏览(47)
  • 最小生成树Kruskal、Prim算法C++

    连通图: 在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1和顶点v2是连通的。如果图中任意一对顶点都是连通的,则称此图为连通图。 生成树: 一个连通图的最小连通子图称作为图的生成树。有 n个顶点 的连通图的生成树有 n个顶点和 n-1 条边。 最小生成树: 最小生活

    2024年02月10日
    浏览(41)
  • 最小生成树(Prim算法与Kruskal算法)

    一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边。我们把构造连通网的最小代价生成树称为最小生成树。 例如下图中①、②、③都是左侧图的生成树,但③是构造连通网的最小代价,所以③是该图的最小生成树。 P

    2024年02月05日
    浏览(58)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包