最小生成树是一种常见的图论算法，是求解无向图最小生成树的问题。它的应用广泛，比如网络设计、路由问题等。在C++中，我们可以使用Kruskal算法或Prim算法来实现最小生成树的求解。

Kruskal算法的基本思想是先把所有边按权值从小到大排序，然后从小到大选择边，如果选择的边不与已选的边构成环，则将它加入最小生成树中，否则，放弃此边。使用并查集来维护连通性，判断边加入是否会导致环的出现。

具体实现过程如下：

1.对图的边按权值从小到大排序；

2.初始化并查集；

3.遍历边集合，如果边的两个端点不在同一个连通块中，则将它们合并，并把此边加入最小生成树中；

4.重复步骤3，直到最小生成树中有n-1条边，n为图中的顶点数。

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

#include

#include

#include

using namespace std;

struct Edge{

  int u, v, w;

  Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}

  bool operator < (const Edge& e)const

    return w < e.w;

};

int find(int x, vector & parent){

  if(parent[x] == x)

    return x;

  return parent[x] = find(parent[x], parent);

}

void unite(int x, int y, vector & parent){

  x = find(x, parent);

  y = find(y, parent);

  parent[x] = y;

}

int kruskal(vector & edges, int n){

  sort(edges.begin(), edges.end());

  vector parent(n);

  for(int i=0; i

    parent[i] = i;

  int cnt = 0, ans = 0;

  for(auto e: edges){

    if(cnt == n - 1)

      break;

    if(find(e.u, parent) != find(e.v, parent)){

      unite(e.u, e.v, parent);

      cnt++;

      ans += e.w;

    }

  }

  return ans;

}

int main(){

  int n, m;

  cin >> n >> m; //n为顶点数，m为边数

  vector edges;

  for(int i=0; i

    int u, v, w;

    cin >> u >> v >> w;

    edges.push_back(Edge(u-1, v-1, w)); //输入顶点、边和权值，编号从1开始，需要减1

  }

  int ans = kruskal(edges, n);

  cout << ans << endl; //输出最小生成树的边权和

  return 0;

}

另外，Prim算法的实现也比较简单。其思想是从一个起点开始，每次找到与当前树最近的一个点加入树中，直到所有的点都被加入。具体实现过程如下：

1.从一个起点开始，将其加入树中；

2.重复以下步骤n-1次，其中n为图的顶点数：

 1）找到与树最近的一个点；

 2）将这个点加入树中；

 3）更新树到其他点的最短距离。

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

#include

#include

#include

#include

using namespace std;

struct Edge{

  int to, w;

  Edge(int _to, int _w): to(_to), w(_w){}

  bool operator > (const Edge& e)const

    return w > e.w;

};

int prim(vector >& adj, int n){

  int ans = 0;

  priority_queue , greater > pq; //小根堆

  vector dist(n, INT_MAX); //到各点最近距离

  vector vis(n);

  dist[0] = 0;

  pq.push(Edge(0, 0));

  while(!pq.empty()){

    Edge e = pq.top();

    pq.pop();

    if(vis[e.to]) continue;

    vis[e.to] = true;

    ans += e.w;

    for(auto ne: adj[e.to]){

      if(!vis[ne.to] && ne.w < dist[ne.to]){

        dist[ne.to] = ne.w;

        pq.push(Edge(ne.to, dist[ne.to]));

      }

    }

  }

  return ans;

}

int main(){

  int n, m;

  cin >> n >> m; //n为顶点数，m为边数

  vector > adj(n);

  for(int i=0; i

    int u, v, w;

    cin >> u >> v >> w;

    adj[u-1].push_back(Edge(v-1, w));

    adj[v-1].push_back(Edge(u-1, w));

  }

  int ans = prim(adj, n);

  cout << ans << endl; //输出最小生成树的边权和

  return 0;

}

综上，C++通过Kruskal算法或Prim算法，可以实现根据图的顶点、边和权值输入，输出最小生成树。这些算法在实际应用中具有重要的意义，可以为网络设计、路由问题等提供有效的解决方案。

相似文章
• Java实现最小生成树算法
  Java实现最小生成树算法
  
  
• Java实现最小生成树算法：Prim和Kruskal
  Java实现最小生成树算法：Prim和Kruskal
  
  

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