Prim算法是一种用于求解最小生成树的经典算法，它的核心思想是贪心策略。在Prim算法中，我们会先选择一个节点作为起点，然后不断地向周围的节点延伸，选择与当前节点相距最近的节点，并将其加入到生成树中。在此基础上，再继续延伸，不断地向周围的节点拓展，直到所有的节点都被加入到生成树中为止。

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

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
const int INF = 0x3f3f3f3f;
int graph[MAXN][MAXN]; // 存储图的邻接矩阵
int dis[MAXN]; // 存储到树的距离
bool vis[MAXN]; // 标记已经加入到生成树中的节点
int prim(int n)
{
  memset(dis, INF, sizeof(dis));
  memset(vis, false, sizeof(vis));
  dis[0] = 0;
  int res = 0;
  for (int i = 0; i < n; i++) {
    int u = -1;
    for (int j = 0; j < n; j++) {
      if (!vis[j] && (u == -1 || dis[j] < dis[u]))
        u = j;
      
    }
    if (u == -1)
      return -1;
    
    vis[u] = true;
    res += dis[u];
    for (int v = 0; v < n; v++) {
      if (!vis[v] && graph[u][v] < dis[v]) {
        dis[v] = graph[u][v];
      }
    }
  }
  return res;
}
int main()
{
  int n, m;
  cin >> n >> m;
  memset(graph, INF, sizeof(graph));
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u - 1][v - 1] = graph[v - 1][u - 1] = w;
  }
  int res = prim(n);
  cout << res << endl;
  return 0;
}

在上述代码中，我们首先定义了一个邻接矩阵来存储图的信息，即 `graph` 数组。接着定义了一个 `dis` 数组，用来记录到生成树的距离。另外，我们还定义了一个 `vis` 数组，用来标记已经加入到生成树中的节点。

在 `prim` 函数中，我们首先对 `dis` 数组和 `vis` 数组进行初始化，并将生成树的根节点设置为第一个节点。接着，我们循环遍历所有节点，找出与当前节点距离最近的未加入到生成树的节点，并将其加入到生成树中。

在加入新节点之后，我们需要再次更新 `dis` 数组，即找出与当前节点相邻的未加入生成树的节点，并计算出它们到生成树的距离。这里，我们使用贪心的策略，选择距离最近的未加入节点，并将其加入到生成树中。

最终，我们返回生成树的权值和，即可得到最小生成树。

相似文章
• C++代码出现coredump问题及不同版本解决方案
  C++
  
  
• C++实现一元二次方程求根公式
  一元二次方程求根公式是高中数学中重要的一部分，它可以用来解决许多实际问题。在计算机科学中，C++
  
  
• C++中的运算顺序：先乘除后加减？
  在C++编程语言中，很多初学者都会产生一个疑问：在运算时，C++的计算顺序究竟是什么样的？到底谁先谁后？这个问题中涉及到了运算符的优先级，也就是运算时优先计算哪个运算符，以及如何理解这些优先级对程序的影响。
  
  
• 如何在C++中输出带百分号的语句
  在C++中输出带百分号的语句可能会让一些刚学习C++的新手困扰，但实际上它并不难实现。本文将介绍如何在C++中输出带百分号的语句。
  
  
• C++编译器手机版的原理解析
  C++编译器是一种用于将C++代码转换成机器码的工具。而现今，由于移动设备的不断普及，人们使用手机来进行编程的需求也越来越高。因此，开发了C++编译器手机版，使人们可以随时随地进行C++编程。
  
  
• C++数据排序实例
  C++是一种非常强大的编程语言，它在数据排序方面也非常出色。通过C++，可以轻松实现各种不同的数据排序算法，以满足不同的需求。
  
  
• C++中使用cin.get()函数
  C++是一种流行的高级编程语言，被广泛用于开发各种应用程序，包括计算机游戏、数据库管理系统、桌面应用程序、网络应用程序等等。C++语言有很多强大的功能，其中一个是cin.get()函数。
  
  
• 如何在C++中按照put顺序输出map？
  在C++中，Map是一个非常有用的容器，它可以存储Key-Value对，并且可以按照Key的顺序来访问Value。但是，当我们想要按照Map中的Put顺序来输出Value时，可能会遇到些许困难。本文将向大家介绍在C++中，按照Map的Put
  
  
• 「C++ Lambda表达式运行速度很慢」
  C++是一种高效的编程语言，但是人们也经常会听到关于Lambda表达式的运行速度很慢的声音。Lambda表达式在C++11中被引入，它是一种匿名函数，允许程序员以一种简洁的方式编写函数对象，同时也可以支持闭包等高级功能。但是，与普通的函数相
  
  
• Java调用C++代码
  Java和C++是两种非常流行的编程语言，各有其优缺点。在开发过程中，我们可能会需要使用Java调用C++的代码。这种情况下，需要使用到Java
  
  
• C++中生成随机数的头文件
  在C++编程中，生成随机数是经常用到的操作，可以用它来模拟实际情况中的随机事件，或是进行随机测试等。为了方便生成随机数，C++提供了一个头文件"random"。
  
  
• C++中如何逐个输出字符串中的字符？
  在C++中，我们可以使用字符串中的循环结构来逐个输出字符串中的字符。
  
  
• C++网络通信技术
  C++网络通信技术是在计算机网络中广泛使用的编程语言之一。它具有跨平台、高效、可靠等特点，可以在多种操作系统和硬件环境下使用。
  
  
• C++ 需要多久学习？
  C++是一种高级编程语言，用于开发各种应用程序，包括游戏、桌面应用程序、嵌入式系统等。C++的学习时间因人而异，取决于个人的背景、学习速度、学习方法等因素。
  
  
• C++编译器是用什么语言实现的？
  C++编译器是一种非常重要的工具，用于将C++代码转换为机器可执行的二进制文件。但是，很多人可能会好奇，C++编译器本身是用什么语言实现的？
  
  
• C++中"main"函数的定义已经存在
  在学习C++中，我们经常会看到一个名为“main”的函数，这个函数通常用于C++程序的入口处，也是程序的执行起点。但是有些人可能会想知道，“main”函数到底是怎么定义的呢？
  
  
• C++ Map的底层数据结构是什么？
  C++中的Map是一个常用的关联容器，用于存储以键值对的方式保存数据。Map容器在使用中并不需要手动分配内存和释放内存，因为底层数据结构是由容器自动管理的。那么Map的底层数据结构是什么呢？
  
  
• C++中封装性的重要性及意义
  在C++中，封装是一种重要的概念，尤其在面向对象编程中尤为显著。它允许我们将一些数据或方法隐藏在类的内部，从而提高代码的安全性、可靠性和重用性。
  
  
• 如何在C++中使用子函数
  在编程中，子函数是一种非常重要的编程概念。它们通常用于将大问题分解为较小的子问题，并遵循单一职责原则（SRP），这可以使代码更容易理解和调试。在C++编程中，子函数可以用来进行各种操作，如打印输出、执行算术运算、进行逻辑判断等等。下面我们将
  
  
• C++中的字符串字面值类（string literal class）
  C++中的字符串字面值类，即string
  
  
• C++语言实现1000以内的完数
  完数是指一个数恰好等于它的因数之和，例如6是一个完数，因为6的因数包括1、2、3，这三个数之和恰好是6。在计算机编程中，寻找完数是一项很有趣和有挑战性的任务，因为这要求我们将计算机理解和求解数学问题相结合。在C++语言中，我们可以写出一个简
  
  
• 「C++必读书籍」知乎讨论
  在计算机科学领域，C++是一种广泛使用的编程语言。对于想要深入学习C++的开发人员来说，了解相关的核心概念和技术是非常重要的。幸运的是，有许多优秀的书籍可以帮助您学习C++编程技巧。在知乎上，也有很多有关C++必读书籍的讨论。
  
  
• 如何在C++的map中根据key删除元素？
  C++的Map是一种非常有用的数据结构，它能够让开发者快速地按照key-value的方式存储和访问数据。然而，有时候我们可能需要从map中删除某个key对应的元素。那么，该如何在C++的map中根据key删除元素呢？
  
  
• C++实现回文串判断
  回文串是指正着和反着读都相同的字符串，比如“level”、“racecar”等。在算法和编程中，判断一个字符串是否为回文串是一项非常基础的任务。在C++语言中，实现回文串判断并不难。本文将介绍一种简单的实现方法。
  
  
• C++求幂运算
  C++是一门广泛应用于计算机科学领域的语言，能够实现许多复杂的运算，包括求幂运算。求幂是指将一个数的指数次方计算出来，例如2的3次方等于8。
  
  
• 「C++教材答案第三版」的整合分享及参考策略
  作为程序员的必备语言，C++一直备受关注和研究。在学习C++的过程中，学生们不可避免地会遇到各种问题和疑问，而教材答案成为解决问题的重要途径。本文将分享教材答案第三版的整合与参考策略，希望能够帮助学生更好地学习C++。
  
  
• 用C++开发音乐播放器
  在今天的数字化时代，音乐已成为人们生活中不可或缺的一部分。越来越多的人喜欢通过音乐来放松心情，享受生活。而随着技术的发展，我们也可以通过各种设备和软件来播放自己喜欢的音乐。本文将介绍如何用C++开发一款简单的音乐播放器。
  
  
• C++贪心算法模板
  在计算机算法的设计中，贪心算法是一种重要的设计思想。在许多情况下，贪心算法能够使算法达到一个较好的近似解，同时具有时间复杂度低的优点。C++
  
  
• C++程序实现高斯消元法计算线性方程组结果
  高斯消元法是一种计算线性方程组结果的有效方法，它可以通过一系列的代数操作将系数矩阵化简为上三角矩阵，从而求解线性方程组的解。在本文中，我们将介绍如何使用C++程序实现高斯消元法，以便更方便地计算线性方程组的结果。
  
  
• C++简易文件复制
  在程序开发过程中，文件复制是经常用到的功能。在C++语言中，可以通过文件流和文件指针的方式实现文件复制。本文主要介绍一种简易的文件复制方法。
  
  
• C++中的pair(a,b)
  在C++中，pair是一个容器，可以使两个不同类型的变量成为一个单元。它的定义如下：
  
  
• C++生成100以内随机数
  生成随机数是C++编程中常用的重要功能之一。在C++中，利用rand()函数可以随机生成整数，本文将介绍如何使用C++生成100以内的随机数。
  
  
• C++ 类的运算符重载
  C++是一门类似于C语言的高级编程语言。它支持面向对象的编程范式，其中一个重要的特性就是运算符重载。运算符重载是将某个运算符的含义扩展到一个自定义类型的对象上的过程。大部分C++经验丰富的程序员都会用运算符重载来简化代码，增强代码可读性和可
  
  
• 如何使用C++将数组存入文件
  在C++中，我们可以将数组存入文件，从而实现数据的永久保存和读取。这在很多应用场景中都非常有用，例如当我们需要在不同的程序之间共享数据时。接下来，我们将介绍如何使用C++将数组存入文件。
  
  
• Visual C++ 2019 X86：强大的编程工具助力开发者
  Visual
  
  
• 如何在C++程序中启动输入法软键盘
  在编写使用C++的程序时，有时需要在程序中启动输入法软键盘以方便用户进行输入。那么，如何在C++程序中启动输入法软键盘呢？下面将详细介绍。
  
  
• Java和C++：哪个更难学？
  Java和C++是两种很受欢迎的计算机编程语言。虽然它们都有各自的优点和用途，但在学习上却各有难点。那么，到底Java和C++哪个更难学呢？
  
  
• C++中声明的对象是否可以被多次创建？
  在C++中，对象是一段具有特定类型的内存区域，其中可以存储数据和方法。声明一个对象就相当于在内存中创建了一个实例，一旦创建，就可以通过访问其成员函数和数据来使用它。
  
  
• C++内存区域的访问效率分析
  对于C++程序的性能优化，内存访问效率是一个不可忽视的因素。因此，理解C++中内存区域的访问效率十分重要。
  
  
• C++ 四舍六入，实现精确的小数运算
  C++
  
  
• C++如何判断字符串的编码格式
  C++是一种高级编程语言，用于开发各种类型的应用程序。在许多情况下，程序员需要了解字符串编码格式，以便正确地处理和转换字符串数据。在本文中，我们将探讨如何使用C++判断字符串的编码格式。
  
  
• C++时间戳转换为日期格式输出
  C++是一种功能强大的编程语言，适用于开发复杂的应用程序。在许多情况下，程序员需要将时间戳转换为日期格式。C++可以通过使用时间戳和时间结构体来完成此任务。在本文中，我们将探讨如何使用C++将时间戳转换为日期格式输出。
  
  
• C++线程调度策略解析
  C++是一门流行的编程语言，为多线程程序提供了强大的支持。线程是一种轻量级的并发机制，允许程序中的多个任务同时运行。C++线程调度策略是多线程程序的核心组成部分，它确定了线程在系统资源中占用的优先级和时间片分配。
  
  
• C++ 实验操作指南
  C++是一种被广泛使用的面向对象编程语言，它可以用来开发各种软件，从简单的控制台程序到复杂的图形用户界面应用程序。在学习C++编程时，进行实验是非常重要的一步，因为它可以让您通过实践来深化对概念的理解并实践解决问题的技能。
  
  
• C++迭代器头文件
  C++的迭代器是其标准模板库中的关键组成部分，用于实现容器的遍历和元素访问。迭代器允许开发人员使用一种统一的方式来处理不同类型的容器，使其具有更高的可复用性和通用性。
  
  
• C++函数模板简介
  C++是一种以函数为基础的编程语言，这使得它非常适合于进行函数模板的开发。函数模板是C++编程语言中的一种特殊用法，它可以将一个通用的函数定义，然后根据不同的情况调用不同的输入参数来解决不同的问题。
  
  
• C++中的哈希表STL实现
  哈希表是一种常见的数据结构，其用途广泛，包括查找、插入、删除等操作。C++中的哈希表STL（Standard
  
  
• C++的基本单元
  C++是一种面向对象的编程语言，是C语言的扩展。它包含了许多基本单元，这些基本单元是构建C++程序的基础。
  
  
• 如何使用C++编写人工智能算法
  人工智能（AI）正在成为越来越多行业中的关键技术。在这个数字时代，AI已经变得更为主流，因为它为用户提供了更好、更快的决策和结果。C
  
  
• C++开发工程师面试经验分享
  作为一名C++开发工程师，曾经在公司的不同部门和项目中进行过多次面试。在这次分享中，我将分享我的一些面试经验，希望对别的C++开发工程师有所帮助。
  
  

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