最小生成树——Prim算法(详细图解)

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

目录

 最小生成树的概念 

 经典题目

prim算法简介 

prim算法解析 (详细图解)

 代码实现

 代码实战


 最小生成树的概念 

在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边,而 w(u, v) 代表此的边权重,若存在 T 为 E 的子集(即)且为无循环图,使得的 w(T) 最小,则此 T 为 G 的最小生成树。最小生成树其实是最小权重生成树的简称。(简而言之就是把一个图变成一棵树,并且树中的边权和最小)

最小生成树——Prim算法(详细图解)

 经典题目

最小生成树——Prim算法(详细图解)

 P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P3366

 (这道题的数据过大,为了简化问题,我们假定数据范围可以用一个二维数组存下)

prim算法简介 

prim算法基于贪心,我们每次总是选出一个离生成树距离最小的点去加入生成树,最后实现最小生成树(不做证明,理解思想即可) 

prim算法解析 (详细图解)

最小生成树——Prim算法(详细图解)

(随机构建一个无向图) 

  • 现在我们构建两个集合S(红色的点),V(蓝色的点),S集合中存放的是已近加入最小生成树的点,V集合中存放的是还没有加入最小生成树的点。显然刚开始时所有的点都在V集合中。
  • 然后们先将任意一个点加入集合S中(默认为点1),并且初始化所有点(除了点1)到集合S的距离是无穷大。

最小生成树——Prim算法(详细图解)

最小生成树——Prim算法(详细图解)

  •  用一个变量res存放最小生成树所有边权值的和。我们每次都选择离S集合最近的点加入S集合中,并且用新加入的点去更新dist数组,因为只有一个新的点加入到集合S中,到集合S的距离才有可能更新(贪心,每次都选最小的)。
  • 更新就是看一下能否通过新加入的点使到达集合的距离变小(看下面dist数组的变化)。
  • 我们开始在加入点1后开始第一次更新。

 最小生成树——Prim算法(详细图解)

  • 现在集合S={1},集合V={2,3,4,5,6,7},根据贪心策略,我们选择离集合S最近的点加入 ,即点2,并把这一条边的权值加到res中。

最小生成树——Prim算法(详细图解)

  • 集合更新为S={1,2},V={3,4,5,6,7},并用点2去更新dist数组,我们发现点3和点7都可以都可以通过边2-3,2-7缩短到集合S得距离。

最小生成树——Prim算法(详细图解)

  • 重复上面的步骤,直到将全部的点加入到最小生成树中。 

最小生成树——Prim算法(详细图解)

最小生成树——Prim算法(详细图解)

最小生成树——Prim算法(详细图解)

  • 3并不能更新任何点 

最小生成树——Prim算法(详细图解)

最小生成树——Prim算法(详细图解)

最小生成树——Prim算法(详细图解)

 最小生成树——Prim算法(详细图解)

最小生成树——Prim算法(详细图解) 最小生成树——Prim算法(详细图解)

  • 这样一颗最小生成树就构建完成了,权值和是57。 

 代码实现

const int MAXN = 1000,INF = 0x3f3f3f3f;//定义一个INF表示无穷大。
int g[MAXN][MAXN],dist[MAXN],n,m,res;
//我们用g[][]数组存储这个图,dist[]储存到集合S的距离,res保存结果。
bool book[MAXN];//用book数组记录某个点是否加入到集合S中。
int main()
{
    cin>>n>>m;//读入这个图的点数n和边数m
    for(int i = 1 ; i<= n ;i++)
    {
        for(int j = 1; j <= n ;j++)
        {
            g[i][j] = INF;//初始化任意两个点之间的距离为正无穷(表示这两个点之间没有边)
        }
        dist[i] = INF;//初始化所有点到集合S的距离都是正无穷
    }
    for(int i = 1; i <= m ; i++)
    {
        int a,b,w;
        cin>>a>>b>>w;//读入a,b两个点之间的边
        g[a][b] = g[b][a] = w;//由于是无向边,我们对g[a][b]和g[b][a]都要赋值
    }
    prim();//调用prim函数
    if(res==INF)//如果res的值是正无穷,表示不能该图不能转化成一棵树,输出orz
        cout<<"orz";
    else
        cout<<res;//否则就输出结果res
    return 0;
}
void prim()
{
    dist[1] = 0;//把点1加入集合S,点1在集合S中,将它到集合的距离初始化为0
    book[1] = true;//表示点1已经加入到了S集合中
    for(int i = 2 ; i <= n ;i++)dist[i] = min(dist[i],g[1][i]);//用点1去更新dist[]
    for(int i = 2 ; i <= n ; i++)
    {
        int temp = INF;//初始化距离
        int t = -1;//接下来去寻找离集合S最近的点加入到集合中,用t记录这个点的下标。
        for(int j = 2 ; j <= n; j++)
        {
            if(!book[j]&&dist[j]<temp)//如果这个点没有加入集合S,而且这个点到集合的距离小于temp就将下标赋给t
            {
                temp = dist[j];//更新集合V到集合S的最小值
                t = j;//把点赋给t
            }
        }
        if(t==-1){res = INF ; return ;}
        //如果t==-1,意味着在集合V找不到边连向集合S,生成树构建失败,将res赋值正无穷表示构建失败,结束函数
        book[t] = true;//如果找到了这个点,就把它加入集合S
        res+=dist[t];//加上这个点到集合S的距离
        for(int j = 2 ; j <= n ; j++)dist[j] = min(dist[j],g[t][j]);//用新加入的点更新dist[]
    }
}

 代码实战

纸上得来终觉浅,绝知此事要躬行,也许看完了上面的解析,你已经最prim算法有了一个大致的了解,学习算法,大致的了解是远远不够的,代码的实践永远是最重要的,学习完一个算法后一定要去自己亲手试试,每个人都有自己的代码风格,大家大可以在自己的风格之上写出自己的prim。

prim习题 简介 难度
P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 模板题 ★☆☆☆☆
P1967 [NOIP2013 提高组] 货车运输 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 基本应用 ★☆☆☆☆
P1991 无线通讯网 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 基本应用 ★☆☆☆☆

 第一题是模板,后面两题主要是更好得帮助我们理解最小生成树——prim在实际和题目中得应用。文章来源地址https://www.toymoban.com/news/detail-407163.html

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

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

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

相关文章

  • 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日
    浏览(39)
  • 最小生成树(Prim算法,Kruskal算法)

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

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

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

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

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

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

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

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

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

    2024年02月05日
    浏览(45)
  • 最小(代价)生成树—Prim算法与Kruskal算法

    目录  一、最小生成树的特点 二、最小生成树算法  ① Prim(普里姆)算法 ②Kruskal(克鲁斯卡尔)算法  ③Prim算法与Kruskal算法对比 最小生成树是带权连通图G=(V,E)的生成树中边的权值之和最小的那棵生成树。它具有以下特点: 图G中各边权值互不相等时有唯一的最小生成树。图

    2024年02月01日
    浏览(35)
  • 图论13-最小生成树-Kruskal算法+Prim算法

    基本思想:按照权值从小到大的顺序选择 n-1 条边,并保证这 n-1 条边不构成回路 具体做法:首先构造一个只含 n 个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中 不产生 回路,直至森林变成一棵树为止。 2.2.1 如果图不联通,直接返回空,该

    2024年02月01日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包