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

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

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

最小生成树

参考博客:图解:什么是最小生成树? - 知乎 (zhihu.com) 

总结下来的过程就是,一张图,我们将他化为树的形式,也就是生成树。那么最小生成树有是啥呢?所谓一个 带权图 的最小生成树,就是原图中边的权值最小的生成树 ,所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。

如何操作才能生成最小生成树?

分为4步:

1. 一开始先随便找一个点(设为x)加入连通集,然后开始遍历其他图中的点

2. 找到离x最近的那个点并且和连通集有联系的点(第一次遍历就是图中和x有边的节点,如果是第n次的话,那么只要和连通集中任一节点有边即可),然后将节点加入连通集。

3.然后更新现在还未加入连通集的节点离连通集的最小距离(因为连通集在第n次遍历之后,其包含的节点也是n个,所以说考量最短节点的时候是要重新算一遍,说的有点抽象,看图)。

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

 4.重复上述3个步骤

为何这样操作就是最小

其实很简单,我们现在设连通集为T,现在有n个还未加入连通集的节点,其中有一个节点a离连通集只有1的距离,其他n-1个节点都离连通集的距离都大于1,此时我们要是不选择a的话,那么等到我们下一次将a选入的时候一定不会比现在选好,举个例子吧,假设一个节点为b,它离连通集的距离为2,然后它离a节点距离为1,我们现在先选b的话,那么带权路径之和res = res + b(2);然后现在将a选入 那么此时 res = res + b(2) + a(1)就增加了3,如果是先选a呢?其实很容易想出来,只增加了2,所以选a一定比选b好,那又有人问了,那万一b和a一样离连通集最近呢?我想说那样的话选谁都一样,选a不会比选b差。

题目详解

其实这道题就是模拟一下上述我写找最小生成树的过程。所以只要将思路理清楚了的话不难写出

1. 一开始先随便找一个点(设为x)加入连通集,然后开始遍历其他图中的点

//把一当成出发点
    dist[1] = 0;

2. 找到离x最近的那个点并且和连通集有联系的点(第一次遍历就是图中和x有边的节点,如果是第n次的话,那么只要和连通集中任一节点有边即可),然后将节点加入连通集。

for(int i=0;i<n;i++){
        int t = -1;
        //找到现在离连通集最近的点:
        //设置一个哨兵dist[t],去和dist[j]中的每个值去比较
        //遍历途中只要小于哨兵的值就将哨兵的值更新成小的那个值
        //但是需要保证现在那个点没有在连通集中。
        for(int j=1;j<=n;j++){
            if(!vis[j]&&(t==-1||dist[t]>dist[j])){
                t = j;
            }
        }
        vis[t] = true;
        if(dist[t]==INF) return INF;
        
        // cout<<"t:"<<t<<"dist[t]:"<<dist[t]<<endl;
        res += dist[t];
}

3.然后更新现在还未加入连通集的节点离连通集的最小距离

for(int j=1;j<=n;j++){
            // cout<<"t:"<<t<<"g[t][j]:"<<g[t][j]<<" ";
            dist[j] = min(dist[j],g[t][j]); 
        }

这样就可以将prim总的代码写出(很重要,需要理解并记住)文章来源地址https://www.toymoban.com/news/detail-467699.html

int Prim(){
    int res = 0;
    memset(dist,0x3f,sizeof(dist));
    //把一当成出发点
    dist[1] = 0;
    for(int i=0;i<n;i++){
        int t = -1;
        //找到现在离连通集最近的点:
        //设置一个哨兵dist[t],去和dist[j]中的每个值去比较
        //遍历途中只要小于哨兵的值就将哨兵的值更新成小的那个值
        //但是需要保证现在那个点没有在连通集中。
        for(int j=1;j<=n;j++){
            if(!vis[j]&&(t==-1||dist[t]>dist[j])){
                t = j;
            }
        }
        vis[t] = true;
        if(dist[t]==INF) return INF;
        
        // cout<<"t:"<<t<<"dist[t]:"<<dist[t]<<endl;
        res += dist[t];
        for(int j=1;j<=n;j++){
            // cout<<"t:"<<t<<"g[t][j]:"<<g[t][j]<<" ";
            dist[j] = min(dist[j],g[t][j]); 
        }
        // cout<<endl;
    }
    return res;
}

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
//存图的连接关系和权重
int g[510][510];
//
int dist[510];
bool vis[510];
int n,m;

int Prim(){
    int res = 0;
    memset(dist,0x3f,sizeof(dist));
    //把一当成出发点
    dist[1] = 0;
    for(int i=0;i<n;i++){
        int t = -1;
        //找到现在离连通集最近的点:
        //设置一个哨兵dist[t],去和dist[j]中的每个值去比较
        //遍历途中只要小于哨兵的值就将哨兵的值更新成小的那个值
        //但是需要保证现在那个点没有在连通集中。
        for(int j=1;j<=n;j++){
            if(!vis[j]&&(t==-1||dist[t]>dist[j])){
                t = j;
            }
        }
        vis[t] = true;
        if(dist[t]==INF) return INF;
        
        // cout<<"t:"<<t<<"dist[t]:"<<dist[t]<<endl;
        res += dist[t];
        for(int j=1;j<=n;j++){
            // cout<<"t:"<<t<<"g[t][j]:"<<g[t][j]<<" ";
            dist[j] = min(dist[j],g[t][j]); 
        }
        // cout<<endl;
    }
    return res;
}

int main(){
    cin>>n>>m;
    //memset 英文:设置
    memset(g,0x3f,sizeof(g));
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        //这一步不是很理解,等会测试一下
        g[a][b] = g[b][a] = min(c,g[a][b]);
        // cout<<g[a][b]<<endl;
    }
    int res = Prim();
    if(res == INF){
        cout<<"impossible";
    }else{
        cout<<res;
    }
    return 0;
}

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

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

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

相关文章

  • 最小生成树——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)
  • 最小生成树(Prim算法与Kruskal算法)

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

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

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

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

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

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

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

    2024年02月01日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包