任务描述 本关任务：以Prim算法获得最小生成树。 相关知识 1．掌握最小生成树的定义和构造方法； 2．掌握最小生成树的两种常用生成算法及效率分析。 测试说明 平台会对你编写的代码进行测试用C语言写： 测试输入： 3 3， a b c a b 3 b c 6 a c 9 预期输出： 边 a--->b 边 b--->c

实现Prim算法的过程如下：

1. 从图中任选一个顶点作为起点，将其加入集合U中。

2. 对于U中的每个顶点v，遍历其所有邻接顶点w：

a. 如果w不在U中，那么将(v,w)边加入候选边集E中。

b. 如果w在U中，忽略这条边。

3. 在E中找到权值最小的边(u,v)，将v加入U中，并将(u,v)加入最小生成树的边集T中。

4. 重复步骤2和3，直到U包含了所有顶点。

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

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

const int INF = 0x3f3f3f3f;

int main() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> edges[n + 1]; // 存储图的邻接表表示
    for (int i = 0; i < m; ++i) {
        char u, v;
        int w;
        cin >> u >> v >> w;
        edges[u - 'a' + 1].push_back({v - 'a' + 1, w});
        edges[v - 'a' + 1].push_back({u - 'a' + 1, w});
    }

    int dist[n + 1]; // 存储当前生成树到每个顶点的最短距离
    bool visited[n + 1]; // 标记每个顶点是否已加入生成树
    memset(dist, INF, sizeof(dist));
    memset(visited, false, sizeof(visited));

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 最小堆
    dist[1] = 0;
    q.push({0, 1}); // 初始时加入起点

    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (visited[u]) continue; // 如果u已经在生成树中，忽略它

        visited[u] = true; // 将u加入生成树中
        if (u != 1) cout << char(u - 1 + 'a') << "--->" << char(dist[u] - 1 + 'a') << endl; // 输出生成树的边
        for (auto [v, w] : edges[u]) {
            if (!visited[v] && w < dist[v]) { // 如果v不在生成树中且(u,v)边权比当前最短距离小
                dist[v] = w;
                q.push({dist[v], v});
            }
        }
    }

    return 0;
}

上述代码中，使用了一个最小堆来存储候选边集E，并按照边权从小到大的顺序弹出最小边。在弹出一个顶点u时，如果u已经在生成树中，忽略它；否则将u加入生成树中，并将(u,v)边加入最小生成树的边集T中。同时，更新当前生成树到每个顶点的最短距离dist数组，并将所有从u出发的边加入最小堆中。