Prim算法是一种常见的最小生成树算法，用于在一个带权连通图中找到一个子图，使得这个子图中所有边的权值之和最小。

C++是一种基于对象的编程语言，广泛应用于计算机科学和编程。下面介绍如何使用C++代码实现Prim算法。

Prim算法的实现步骤如下：

1. 选定一个任意顶点作为起点，加入到生成树中。

2. 在未加入生成树的点集中，选取与生成树中任意一个点相连的权值最小的点，并将这个点加入到生成树中。

3. 重复步骤2，直至所有点都加入到生成树中。

下面是用C++代码实现Prim算法的示例程序：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=100010,INF=1<<30;
int head[MAXN],en[MAXN<<1],cap[MAXN<<1],dis[MAXN],nxt[MAXN<<1],tot=1,s,t,vis[MAXN],n,m;
void add(int u,int v,int c){
  en[++tot]=v;
  cap[tot]=c;
  nxt[tot]=head[u];
  head[u]=tot;
  en[++tot]=u;
  cap[tot]=0;
  nxt[tot]=head[v];
  head[v]=tot;
}
struct node{
  int w,id;
  bool operator<(const node& o)const
    return w>o.w;
  
};
priority_queue<node>Q;
void prim(int s){
  for(int i=1;i<=n;i++)dis[i]=INF;
  dis[s]=0;
  Q.push(nodes);
  while(!Q.empty()){
    int x=Q.top().id;Q.pop();
    if(vis[x])continue;
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i]){
      int y=en[i];
      if(cap[i]&&dis[y]>cap[i]){
        dis[y]=cap[i];
        Q.push(node{dis[y],y});
      }
    }
  }
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    int u,v,c;
    cin>>u>>v>>c;
    add(u,v,c);
    add(v,u,c);
  }
  prim(1);
  int ans=0;
  for(int i=1;i<=n;i++)ans+=dis[i];
  cout<<ans<<endl;
  return 0;
}

以上代码中，首先定义了图的头结点，边端点和边权值数组，记录顶点是否已经加入的vis数组。

add函数用于添加边，由于Prim算法是针对无向图的，因此每条边应该添加两次。

prim函数用于实现Prim算法，首先将所有顶点的距离dis初始化为INF，将起点s加入优先队列中，并将其dis设置为0。

接着，每次从优先队列中取出距离最小的顶点x，并标记vis[x]=1。遍历与x相连的顶点y，如果边x->y未被访问且dis[y]>cap[i]，则将dis[y]更新为cap[i]，并将(y,dis[y])加入优先队列中。

最后，prim函数结束时所有点都已被加入到生成树中，dis数组记录了每个点到生成树上的最短距离。通过计算dis数组的和，可以得到生成树的最小权值和。

以上就是使用C++代码实现Prim算法的过程和示例程序。使用Prim算法可以有效地求解最小生成树，而C++语言提供了丰富的工具和类库，使得编写高效的算法代码变得更加容易。

相似文章
• C++代码实现三角形面积计算
  C++是一种高级编程语言，广泛用于软件开发和计算机科学。其中一个常见的应用是计算三角形的面积。在这篇文章中，我们将介绍如何使用C++编写一个简单的程序来计算三角形的面积。
  
  
• C++ 绘制矩形的代码
  C++是一种流行的编程语言，广泛用于开发各种应用程序，游戏和其他高级软件。在C++中，绘制矩形是一种常见的图形操作，可以通过使用图形库和一些代码来实现。下面是一个简单的C++代码，可以绘制一个基本的矩形。
  
  
• C++多线程循环打印ABC十次
  在C++编程中，多线程技术的应用越来越重要。本文将介绍如何使用C++多线程循环打印ABC十次。
  
  
• C++静态多态的实现方式和应用场景解析
  C++是一种支持静态多态的编程语言，实现多态的方式主要有两种：重载和模板。在不同的场景下，两种方式都有各自的优劣势。
  
  
• C++中的char数据类型是什么？
  C++中的char数据类型是一种基本数据类型，它代表的是单个字符的数据。在C++中，char类型的变量只能存储一个字符，并且必须用单引号将字符括起来。
  
  
• C++编写比较两个数是否相等的函数
  当我们在进行编程时，经常需要比较两个数是否相等。为了方便代码的复用和维护，我们可以编写一个函数来实现该功能。下面是使用C++语言编写比较两个数是否相等的函数的示例代码：
  
  
• C++ 整型转字符型的方法
  在
  
  
• Rust和C++的学习曲线有多陡峭？
  Rust和C++是两种高级编程语言，常用于系统级编程和底层开发。二者的学习曲线可以说是相对陡峭的。不过，这也并不意味着学习难度过大，只是需要有一些耐心和耐心。
  
  
• C++中list的遍历方法
  在C++中，list是一种非常常用的数据结构，可以用于存储多个元素，并且支持动态添加、删除操作。在使用list时，遍历列表是一种非常常见的操作。本文将介绍C++中list的遍历方法。
  
  
• C++动态规划实现背包问题在货币系统中的应用
  背包问题是解决最优化问题中的经典问题之一。在货币系统中，找零问题就是背包问题的一个典型案例。使用C++动态规划算法实现背包问题，在货币系统中的应用可以使找零问题更加有效和准确。
  
  
• C++函数中的静态关键字static
  C++编程语言中的静态关键字static是一种非常有用的语言元素。它可以用于函数、全局变量和局部变量中。
  
  
• 如何在c++中提取字符串的特定字符位置？
  在C++中，我们可以使用字符串类（string
  
  
• C++多组数据输入输出
  在C++程序中，我们经常会遇到需要输入和输出多组数据的情况。如何进行高效的多组数据输入输出，是大多数程序员需要解决的问题。
  
  
• C++中的输入输出语句
  C++中的输入输出语句是程序设计中必不可少的部分。输入语句用于从键盘或外部文件中读入数据，输出语句则用于将程序处理后的数据输出至屏幕或文件中。C++提供的输入输出语句非常灵活，但在使用时需要特别注意以下几点：
  
  
• C++打包DLL文件
  C++是一种常用的编程语言，其应用范围十分广泛。在开发过程中，有时候需要将一些常用的功能封装成DLL文件，方便重复使用。那么，如何打包C++的DLL文件呢？
  
  
• C++ 如何自动将 double 数据输出补零？
  C++
  
  
• C++中while循环的用法
  C++语言中的while循环是一种条件循环语句，可以重复执行一段代码直到指定的条件不再成立为止。它的语法形式如下：
  
  
• C++虚函数原理解析：实现多态的关键
  在C++中，虚函数是实现多态的关键。虚函数是在基类中定义的一种函数，它的行为可以在派生类中被重新定义。这个特性允许一个函数在运行时解决到底调用哪一个函数。
  
  
• 如何在c++中控制while循环的时间？
  在编写C++程序时，while循环是常见的控制流程语句之一。尽管while循环是一种非常有用的方法来控制代码的执行，但有时我们需要在while循环中控制代码执行的时间。本篇文章将介绍几种在C++中控制while循环时间的方法。
  
  
• C++运行程序出错！
  C++作为一种流行的编程语言，在软件开发中得到了广泛应用。然而，即使是经验丰富的程序员，在编写C++程序的过程中也难免会遇到一些错误。特别是在程序运行时出现错误，这往往会让程序员感到非常困惑和困扰。
  
  
• C++中重载函数的意义和作用是什么？
  C++是一种基于面向对象的编程语言，具有强大的函数重载功能。函数重载是指在程序中定义多个名称相同但参数类型和个数不同的函数。重载函数的作用在于提高程序的复用性和可读性。
  
  
• C++工程师需要考取哪些证书？
  在当今互联网时代，C++成为了非常重要的一门编程语言，其应用场景广泛，很多企业都在招聘C++工程师。考取一些与C++相关的证书是提高职业发展和获得更好工作的有效途径。那么，作为一名C++工程师，需要考取哪些证书呢？
  
  
• 蓝桥杯C++初级组真题：简体中文版
  蓝桥杯是全国性的计算机竞赛，被誉为计算机行业的奥林匹克竞赛。C++初级组是蓝桥杯比赛的一个级别，针对的是具备一定编程基础的初学者。在这篇文章中，我们将针对蓝桥杯C++初级组真题进行讲解。
  
  
• C++通讯录管理系统设计
  C++通讯录管理系统设计是一个用于管理通讯录的软件，旨在提高工作效率和减少人工错误。本文将介绍如何用C++语言设计并实现一个通讯录管理系统，具体包括系统需求分析、系统设计和系统实现等方面。
  
  
• "C/C++ B组语言在蓝桥杯比赛中的默认语言是什么？"
  蓝桥杯是一项全国性的计算机比赛，也是许多计算机爱好者的重要竞赛。在这场比赛中，C/C++语言是比赛的常用语言之一。对于参赛者而言，要熟练掌握C/C++语言是非常重要的。但是，在蓝桥杯比赛中，C/C++还有很多细节需要注意，比如B组语言的默认
  
  
• 《数据结构算法与应用：C++语言描述（第一版）》答案
  《数据结构算法与应用：C++语言描述（第一版）》是一本非常有价值的书籍，它涵盖了数据结构和算法的基础知识，介绍了C++语言在数据结构实现中的应用。这本书对于计算机专业学生和从事软件开发的程序员来说都是非常有用的。
  
  
• C++中单引号与双引号的用法区别
  单引号和双引号都是C++中表示字符或字符串的符号，但它们的用法有很大的差异。
  
  
• C++编程的作用是什么？
  C++编程是一种高级编程语言，它具有广泛的应用范围。C++编程语言提供了一种高效的编程体验，可以用来创建各种类型和大小的程序，从操作系统到游戏、工具和应用程序都可以用C++编写。
  
  
• C++里的函数重载是什么？
  C++语言是一种强大的编程语言，它有许多特性和功能可以支持程序员进行高效的编程工作。其中一个非常实用的特性就是函数重载。
  
  
• C++中未经处理的异常：原因、影响和应对策略
  C++是一门广泛应用于系统开发、游戏开发、图形图像处理等领域的高级编程语言，但在编写C++程序时，经常会遇到未经处理的异常。这些异常可能导致程序的不可预测行为，甚至奔溃，给程序员带来巨大的麻烦。因此，了解未经处理的异常的原因、影响和应对策略
  
  
• C++如何求一个整数的位数
  在C++中，它提供了一些简单而有用的内置函数来计算一个整数的位数。我们可以使用这些内置函数来轻松地计算一个整数的位数。
  
  
• C++中的stoi和atoi函数
  C++是一种编程语言，其提供了许多方便的函数来处理字符串和数字。stoi和atoi函数就是其中最常用的两种函数。
  
  
• C++中空格怎样表示？
  在C++中，空格是可以用来分隔各个关键字、标识符和操作符的。空格可以被任意多次使用来实现更加美观、易于阅读的代码。
  
  
• C++成绩等级表示
  C++是一门非常流行的编程语言，它在程序设计中广泛使用。C++编程语言可以应用于各种领域，如计算机科学、金融、物理学、生物学、航天等。在学习C++编程时，分数等级表示是一种非常有用的技巧。
  
  
• C++ deque的遍历方法
  C++
  
  
• C++输入语法详解
  C++是一种广泛使用的编程语言，它有很多语法规则和特定的输入方式，这些输入方式在编写程序时是非常重要的。本文将对C++的输入语法进行详解。
  
  
• 初学者C++测试：适合小学生入门
  C++是一种高级编程语言，适用于各种应用程序开发。而在当今数字时代，计算机科学和编程能力已经成为不可避免的技能。因此，许多年轻人都希望得到一些编程经验。但是，对于初学者而言，C++的复杂性可能会让他们望而却步。那有什么方法可以帮助初学者获得
  
  
• C++资格认证证书
  C++是一种广泛使用的编程语言，对于想要进入编程行业的人来说，掌握C++是必不可少的。然而，掌握一门语言并不意味着你已经具备了所有编程方面的技能。为了进一步证明您的专业知识和技能，您可以通过C++资格认证考试获得C++资格认证证书。
  
  
• C++字符串输入输出详解
  C++是一门强大的编程语言，它具有许多特性和功能，其中字符串的输入输出是非常重要的部分。在本文中，我们将为您介绍C++中字符串的输入输出方法及其详解。
  
  
• C++矩阵库比较
  C++矩阵库是一个非常重要的工具，在计算机图形学、信号处理、机器学习等领域有广泛的应用。目前市面上有许多C++矩阵库可供选择，这些库各自具有不同的特点和优势。本文将介绍几种常用的C++矩阵库，以帮助读者选择适合自己需求的库。
  
  
• 如何解决C++代码无法生成问题
  C++代码无法生成是一个非常常见的问题，通常会在编译代码时出现。如果你遇到了这个问题，那么你不必担心，因为它通常可以通过一些简单的方法来解决。
  
  
• 如何获取Visual C++的注册密钥？
  Visual
  
  
• 如何解决Dev C++下载失败的问题？
  Dev
  
  
• 微软C++是否可卸载？
  微软C++是一种广泛使用的编程语言，被用于开发各种应用程序和系统软件。然而，一些用户可能会有这样的疑问：微软C++是否可以卸载？
  
  
• 使用C++编写文件加密解密程序
  在现代社会中，越来越多的人都开始关注自己的数据安全。当我们需要保护我们重要的数据资料时，通常的方法就是使用文件加密来保护私密性。文件加密是一种将数据转化为另一种形式的技术，从而使数据在未经批准的情况下不能被访问或读取。
  
  
• C++如何保留小数点？
  C++是一种广泛使用的编程语言，程序员们经常需要对数字进行精确的计算和输出。而保留小数点是一个重要的技巧，在很多实际应用中都非常有用。下面我们就来讨论一下C++如何保留小数点。
  
  
• C++消息通信：如何实现多线程间的数据传输和共享？
  在C++中，多线程编程已经成为了非常普遍的需求，但是由于多个线程同时运行，这就使得很多时候需要通过消息通信来实现线程间的数据传输和共享。那么在C++中如何实现多线程间的消息通信呢？
  
  
• C++中使用对象数组作为函数参数
  在C++中，对象数组是一种非常方便的数据结构，它能够轻松地存储和操作多个对象的数据。使用对象数组作为函数参数，可以使代码更加简洁、高效且易于维护。
  
  
• 使用C++编写小波时频图——一步步教你实现！
  小波时频分析是一种用于信号处理的方法，它能够通过对信号进行小波变换，得到信号各个频率分量在时间轴上的变化情况。在实际应用中，小波时频分析广泛应用于语音识别、压缩和图像处理等领域。
  
  
• 如何选择适合自己的C++学习机构？
  随着计算机科学的发展，C++已成为一种非常流行的编程语言。如果你想学习C++，你会发现市场上有很多不同的学习机构和课程。然而，如何选择适合自己的C++学习机构是非常关键的。在这篇文章中，我们将为你提供一些实用的建议。
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政