Prim算法C++代码 |21xrx.com

Prim算法C++代码

2023-07-01 09:56:44 深夜i -- --

Prim算法 C++ 代码

Prim算法是一种常见的用于解决最小生成树问题的算法，它可以保证生成的树权值最小。

下面是Prim算法的C++代码实现：


const int INF = 0x3f3f3f3f; // 表示无穷大
int n; // 点的数量
int g[N][N]; // 保存图的邻接矩阵
bool st[N]; // 标记每个点是否已经加入生成树
int dist[N]; // 保存树上每个点和非树上点的最小距离
int prim() {
  memset(dist, 0x3f, sizeof dist); // 初始化树上每个点和非树上点的最小距离为无穷大
  int res = 0; // 记录生成树的权值之和
  for (int i = 0; i < n; i++) { // 从第一个点开始建立生成树
    int t = -1; // 记录非树上点中距离树最近的点
    for (int j = 0; j < n; j++) {
      if (!st[j] && (t == -1 || dist[j] < dist[t])) // 如果该点未加入树中且距离树最近
        t = j;
      
    }
    if (i && dist[t] == INF) 返回无穷大
    
    if (i) { // 如果不是第一个加入树中的点，则将该点和距离树最近的点之间的边加入生成树
      res += dist[t];
    }
    for (int j = 0; j < n; j++) { // 更新距离树上每个点和非树上点的最小距离
      dist[j] = min(dist[j], g[t][j]); // 如果原来的距离大于新添加的边权，就更新距离
    }
    st[t] = true; // 将该点加入树中
  }
  return res; // 返回生成树的权值之和
}

在上面的代码中，我们先初始化树上每个点和非树上点的最小距离为无穷大。然后从第一个点开始建立生成树，在循环中，我们找到非树上点中距离树最近的点，在将该点和距离树最近的点之间的边加入生成树。接着，我们更新距离树上每个点和非树上点的最小距离，将该点加入树中。最后，我们返回生成树的权值之和。

Prim算法的时间复杂度为O(n^2)，因为在每次循环中，我们需要遍历每个点找出非树上点中距离树最近的点。如果使用堆优化，可将时间复杂度降为O(mlogn)，其中m为边数。

总之，Prim算法是解决最小生成树问题的一种高效算法，可以帮助我们解决许多实际问题。

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

下一篇: C++类的初始化

评论区

()

相似文章