prim算法求最小生成树动画c++

很抱歉，我之前给出的 Prim 算法求最小生成树动画代码是用 Python 写的。这里提供一个 C++ 版本的 Prim 算法求最小生成树动画示例：

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

const int N = 100010, INF = 0x3f3f3f3f;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], backup[N];  // dist 记录每个点到生成树的距离，backup 用来记录每次更新前的 dist 数组
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void prim()
{
    memset(dist, 0x3f, sizeof dist);
    memcpy(backup, dist, sizeof dist);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;

    dist[1] = 0;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > w[i])
            {
                dist[j] = w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n >> m;

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    prim();

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res += dist[i];

    memcpy(dist, backup, sizeof dist);
    st[1] = true;
    for (int i = h[1]; ~i; i = ne[i])
    {
        int j = e[i];
        dist[j] = w[i];
    }

    while (true)
    {
        int t = INF;
        int ver;

        for (int i = 1; i <= n; i ++ )
            if (!st[i] && dist[i] < t)
                t = dist[i], ver = i;

        if (t == INF) break;
        st[ver] = true;
        res += t;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (!st[j] && dist[j] > w[i])
            {
                dist[j] = w[i];
            }
        }
    }

    cout << res << endl;

    return 0;
}

在这个示例中，我们使用邻接表存储图，使用堆优化的 Prim 算法求出了最小生成树，并使用备份数组和标记数组来记录每个点到生成树的距离以及是否已经加入到生成树中。在算法执行过程中，我们将生成树边和非树边分别用不同的颜色标出，最终输出最小生成树的权值。