Prim算法求最小生成树

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

一.最小生成树

给定一张边带无权的无向图G = (V, E), n = |V|, m = |E|。由V中全部n个顶点和E中n - 1条边构成的无向连通子图被称为G的一课生成树。边的权值之和最小的生成树被称为无向图的最小生成树。

二.算法描述

Prime算法

Prim算法总是维护最小生成树的一部分。最初,Prim算法仅确定1号节点属于最小生成树。
1.在任意时刻,设已经确定属于最小生成树的节点集合为T,剩余节点集合为S。Prim算法找到两点端点分别属于集合S,T的权值最小的边,然后把点x从集合S中删除,加入到集合T,并把权值累加到答案中。
2.具体来说,可以维护数组d:若x属于S,则d[x]表示节点x与集合T中的节点之间权值最小的边的权值。若x属于T,则d[x]就等于x被加入T时选出的最小的边的权值。
可以类比Dijkstra算法,用一个数组标记节点是否属于T。每次从未被标记的节点中选出d值最小的,把它标记(新加入T),同时扫描所有出边,更新另一个端点的d值。最后,最小生成树的权值总和就是d[x](∑ x = 2~n)。
3.Prim算法的时间复杂度为O(n^2),可以用二叉堆优化到(mlogn),但用二叉堆优化不如直接使用Kruskal算法更加方便。因此,Prim主要用于稠密图,尤其是完全图的最小生成树的求解。

示例

编写程序用prim算法求解最小生成树,算法,算法,图论,数据结构
图的初始状态,将d数组全部设为无穷大。

编写程序用prim算法求解最小生成树,算法,算法,图论,数据结构
编写程序用prim算法求解最小生成树,算法,算法,图论,数据结构
编写程序用prim算法求解最小生成树,算法,算法,图论,数据结构

编写程序用prim算法求解最小生成树,算法,算法,图论,数据结构
编写程序用prim算法求解最小生成树,算法,算法,图论,数据结构
编写程序用prim算法求解最小生成树,算法,算法,图论,数据结构
编写程序用prim算法求解最小生成树,算法,算法,图论,数据结构
编写程序用prim算法求解最小生成树,算法,算法,图论,数据结构
每次找到集合T外距离集合T最近的点x,用x更新其他点到集合T的距离,当所有点不连通时,不存在最小生成树,即当更新过程中d[x] = inf,当所有的点都被加进集合T中,存在最小生成树。
上述示例最小生成树的树边权重之和为 4 + 8 + 1 + 2 + 4 + 2 + 7 + 9 = 37文章来源地址https://www.toymoban.com/news/detail-524549.html

三.代码示例

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;
int g[N][N], dist[N];
int n, m;
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
                
        st[t] = true;
        if(i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
        if(i) res += dist[t];
        
        for(int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = g[b][a] = min(g[a][b], w);
    }
    
    int t = prim();
    if(t == 0x3f3f3f3f) puts("impossible");
    else printf("%d", t);
    return 0;
 }

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

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

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

相关文章

  • 考研算法复试刷题19天:Prim算法求最小生成树 【prim,最小生成树】

    参考博客:图解:什么是最小生成树? - 知乎 (zhihu.com)  总结下来的过程就是,一张图,我们将他化为树的形式,也就是生成树。那么最小生成树有是啥呢? 所谓一个 带权图 的最小生成树,就是原图中边的权值最小的生成树 ,所谓最小是指边的权值之和小于或者等于其它

    2024年02月07日
    浏览(63)
  • 最小生成树—Prim算法

    我们要讨论的问题是如何在一个 无向图 中找到它的最小生成树,虽然这个问题对有向图也有意义,但是处理起来更麻烦。 一个无向图 G 的最小生成树就是连接 G 上所有顶点的边构成的树,且这些边的总权值最低。当且仅当图是 连通的 才有最小生成树。 在无向图的最小生成

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

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

    2024年02月01日
    浏览(50)
  • Prim算法求最小生成树

    给定一张边带无权的无向图G = (V, E), n = |V|, m = |E|。由V中全部n个顶点和E中n - 1条边构成的无向连通子图被称为G的一课生成树。边的权值之和最小的生成树被称为无向图的最小生成树。 Prim算法总是维护最小生成树的一部分。最初,Prim算法仅确定1号节点属于最小生成树

    2024年02月12日
    浏览(41)
  • 最小生成树——prim算法实现

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

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

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

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

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

    2024年02月08日
    浏览(43)
  • 最小生成树——Prim算法(详细图解)

    目录  最小生成树的概念   经典题目 prim算法简介  prim算法解析 (详细图解)  代码实现  代码实战 在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边,而 w(u, v) 代表此的边权重,若存在 T 为 E 的子集(即)且为无循环图,使得的 w(T) 最小,则此 T 为 G 的

    2023年04月09日
    浏览(39)
  • 最小生成树——普利姆(Prim)算法

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

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

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

    2024年02月08日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包