C++ Prim算法解析 |21xrx.com

C++ Prim算法解析

2023-07-11 13:13:14 深夜i 17 0

C++ Prim算法最小生成树图论

Prim算法是一种用来解决最小生成树问题的贪心算法。该算法以一个起始节点开始，逐步扩展生成树，直到覆盖所有节点，且边的权重和最小。

C++ Prim算法实现基本步骤如下：

1. 创建一个包含所有节点的集合G和一个空集合T作为生成树

2. 从集合G中选择一个节点作为起点，并将该节点添加到集合T中

3. 从集合G中选择连接T中节点和G中节点的最小边，并将该边添加到生成树T中

4. 重复步骤3，直到生成树T中包含所有节点

下面是基于邻接矩阵实现Prim算法的C++代码：

#include <iostream>
#include <vector>
#define INF 0x7fffffff
using namespace std;
vector<vector<int>> G; // 存储图的邻接矩阵
// Prim算法函数
void prim(int start_node, int node_num){
  vector<int> lowcost(node_num, INF); // 存储未加入生成树的节点到生成树中的最小距离(权重)
  vector<int> closest(node_num, start_node); // 存储当前节点最近的生成树中节点
  vector<bool> visited(node_num, false); // 存储节点是否加入生成树
  visited[start_node] = true;
  int edge_num = 1; // 记录生成树中已经有的边数
  // 初始化lowcost和closest
  for(int i=0;i<node_num;i++){
    lowcost[i] = G[start_node][i];
    closest[i] = start_node;
  }
  while(edge_num < node_num){
    int min_weight = INF;
    int close_node = -1;
    // 找到当前未加入生成树的节点到生成树中的最小距离
    for(int i=0;i<node_num;i++){
      if(!visited[i] && lowcost[i]<min_weight){
        min_weight = lowcost[i];
        close_node = i;
      }
    }
    visited[close_node] = true;
    edge_num++;
    // 更新lowcost和closest
    for(int i=0;i<node_num;i++){
      if(!visited[i] && lowcost[i]>G[close_node][i]){
        lowcost[i] = G[close_node][i];
        closest[i] = close_node;
      }
    }
  }
  // 输出生成树
  for(int i=0;i<node_num;i++){
    if(closest[i]!=i){
      cout<<closest[i]<<" "<<i<<" "<<G[closest[i]][i]<<endl;
    }
  }
}
int main()
{
  int node_num, edge_num;
  cin>>node_num>>edge_num;
  G.resize(node_num, vector<int>(node_num, INF));
  // 输入邻接矩阵
  for(int i=0;i<edge_num;i++){
    int u, v, w;
    cin>>u>>v>>w;
    G[u][v] = w;
    G[v][u] = w;
  }
  int start_node;
  cin>>start_node;
  prim(start_node, node_num);
  return 0;
}

以上是C++ Prim算法的实现，该算法时间复杂度为O(n^2)，在稠密图中表现良好，但在稀疏图中效率较低，应该优先考虑使用Kruskal算法。

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

下一篇: C++编写的DLL文件是否可查看源代码？

评论区

相似文章