通过c++语言使用贪心算法解决最小生成树问题

最小生成树问题是图论中的经典问题之一，可以使用贪心算法求解。下面是基于Prim算法的C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f; // 无穷大
const int MAXN = 10005; // 最大顶点数

struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

vector<Edge> graph[MAXN]; // 图的邻接表存储
int dis[MAXN]; // 存储已选中的点到未选中的点的最小距离
bool vis[MAXN]; // 记录是否已选中

int prim(int s, int n) {
    memset(vis, false, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    pq.push(make_pair(0, s));
    int ans = 0;
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        ans += dis[u];
        for (int i = 0; i < graph[u].size(); ++i) {
            int v = graph[u][i].to;
            int w = graph[u][i].weight;
            if (!vis[v] && w < dis[v]) {
                dis[v] = w;
                pq.push(make_pair(dis[v], v));
            }
        }
    }
    return ans;
}

int main() {
    int n, m; // n为顶点数，m为边数
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w; // u, v为边的两个顶点，w为边的权值
        cin >> u >> v >> w;
        graph[u].push_back(Edge(v, w));
        graph[v].push_back(Edge(u, w)); // 无向图需要将边反向加入邻接表
    }
    int ans = prim(1, n); // 从顶点1开始
    cout << ans << endl;
    return 0;
}

该代码使用了邻接表存储图，利用priority_queue实现了Prim算法。其中dis数组存储已选中的点到未选中的点的最小距离，vis数组记录是否已选中。在每次从优先队列中取出一个点u时，遍历u的所有邻边v，如果v未被选中且u到v的距离小于dis[v]，则更新dis[v]并将v加入优先队列。最终答案为dis数组中所有非无穷大元素之和。

需要注意的是，该代码假设图是联通的。如果图不是联通的，需要对每个连通块分别执行Prim算法。