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

C++语言实现Prim算法的代码

2023-07-04 21:09:53 深夜i -- --

C++ Prim算法代码实现

Prim算法是一种经典的最小生成树算法，它可以在图中找到一棵生成树，使得这棵生成树的边权之和最小。在实际应用中，Prim算法被广泛应用于路由协议、网络设计等领域。

C++语言实现Prim算法的代码如下：


#include <iostream>
#include <cstring>
using namespace std;
#define maxn 1005
#define INF 0x3f3f3f3f
int g[maxn][maxn]; // 图的邻接矩阵
int dist[maxn]; // 距离数组，记录当前点到其他点的最小距离
bool vis[maxn]; // 记录每个点是否已访问
int prim(int n)
{
  memset(vis, false, sizeof(vis)); // 初始化所有点为未访问
  memset(dist, INF, sizeof(dist)); // 初始化所有距离为无穷大
  dist[1] = 0; // 以1号点为起点开始遍历
  int ans = 0;
  for(int i = 1; i <= n; i++)
  {
    int u = 0; // 定义一个变量u记录当前未访问的距离最小的点
    for(int j = 1; j <= n; j++)
      if(!vis[j] && (u == 0 || dist[j] < dist[u]))
        u = j;
    vis[u] = true; // 记录当前点为已访问
    ans += dist[u]; // 加入该点到生成树里的边权值
    for(int j = 1; j <= n; j++)
      if(!vis[j] && dist[j] > g[u][j]) // 更新当前点到未访问点的距离
        dist[j] = g[u][j];
  }
  return ans;
}
int main()
{
  int n, m; // n表示点的个数，m表示边的个数
  cin >> n >> m;
  memset(g, INF, sizeof(g)); // 初始化邻接矩阵
  for(int i = 1; i <= m; i++)
  {
    int u, v, w; // 连接u和v两点的边权为w
    cin >> u >> v >> w;
    g[u][v] = g[v][u] = w; // 无向图
  }
  int ans = prim(n);
  cout << ans << endl;
  return 0;
}

以上就是C++语言实现Prim算法的代码，我们从主函数开始分析。

1. 输入点和边的个数n、m；

2. 初始化邻接矩阵g；

3. 循环m次输入边的信息，并用邻接矩阵存储；

4. 调用prim(n)函数，返回最小生成树的边权之和；

5. 输出最小生成树的边权之和。

在prim函数中，我们使用邻接矩阵存储图，使用dist数组存储当前点到其他点的最小距离，使用vis数组记录每个点是否已访问。首先，我们初始化dist数组和vis数组。接着，以1号点为起点开始遍历，按照贪心的思想，每次选择距离最小的未访问点加入生成树中，并更新距离数组dist。直到所有点均被访问，返回最小生成树的权值。

C++语言实现Prim算法的代码比较简单，容易理解，也易于实现。它是求解最小生成树问题的一个良好算法，在实际应用中具有很高的价值。

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

下一篇: C++验证3n+1问题

评论区

()

相似文章