C++语言实现prim算法代码 |21xrx.com

C++语言实现prim算法代码

2023-07-08 00:52:17 深夜i 25 0

C++ Prim算法代码实现

prim算法，又称为普里姆算法，是一种常用的最小生成树算法。它的基本思路是从一个起始点开始，找到最短边的相邻点加入到生成树中，然后继续从生成树的边中找出最短的边连接一个新的点，直至所有的点都被连接为止。

在C++语言中，实现prim算法，需要定义一个图的邻接矩阵（或邻接表）来存储图的信息，然后按照prim算法的步骤进行处理。下面是一个使用C++语言实现prim算法代码的示例：

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 10005;
int n, m; // n为图中节点数，m为边数
int g[MAXN][MAXN]; //邻接矩阵存储图
int dist[MAXN]; //每个节点到生成树的最短边权值
bool vis[MAXN]; //标记节点是否已经放入生成树中
void prim(int s) //从节点s开始，实现prim算法
{
  memset(dist, 0x3f, sizeof(dist)); //初始化dist数组，赋值为无穷大
  dist[s] = 0; //起始节点到自己的距离为0
  for (int i = 1; i <= n; i++) //遍历每个节点，将其加入生成树
  {
    int u = -1;
    for(int j = 1; j <= n; j++) //找到dist最小的节点，将其加入生成树
    {
      if (!vis[j] && (u == -1 || dist[j] < dist[u]))
      
        u = j;
      
    }
    vis[u] = true; //将节点u加入生成树
    for(int v = 1; v <= n; v++) //更新剩余节点到生成树的距离
    {
      if (!vis[v] && dist[v] > g[u][v])
      {
        dist[v] = g[u][v];
      }
    }
  }
}
int main()
{
  cin >> n >> m; //读入节点数和边数
  memset(g, 0x3f, sizeof(g)); //初始化邻接矩阵，赋值为无穷大
  for(int i = 1; i <= m; i++)
  {
    int x, y, w;
    cin >> x >> y >> w;
    g[x][y] = g[y][x] = w; //存储边的信息到邻接矩阵
  }
  prim(1); //从节点1开始，实现prim算法
  int ans = 0;
  for(int i = 1; i <= n; i++) //统计生成树的边权值之和
  {
    ans += dist[i];
  }
  cout << ans << endl; //输出生成树的边权值之和
  return 0;
}

在C++语言中，使用邻接矩阵（或邻接表）实现图的存储和处理，能够方便地实现prim算法。在实际编程中，根据具体问题的需求定义相应的数据结构和算法，可以提高代码的效率和可读性。

上一篇: idea打包java可执行jar包

下一篇: C++读取表格教程

评论区

相似文章